Support Base 64 URL

[commonsensesoftware]

Updated by @MihaZupan on 2024-02-27

Proposed API

namespace System.Buffers.Text;

public static class Base64Url
{
    // Encode bytes => utf8
    public static OperationStatus EncodeToUtf8(ReadOnlySpan<byte> bytes, Span<byte> utf8, out int bytesConsumed, out int bytesWritten, bool isFinalBlock = true);
    public static OperationStatus EncodeToUtf8InPlace(Span<byte> buffer, int dataLength, out int bytesWritten);

    // Decode from utf8 => bytes
    public static OperationStatus DecodeFromUtf8(ReadOnlySpan<byte> utf8, Span<byte> bytes, out int bytesConsumed, out int bytesWritten, bool isFinalBlock = true);
    public static OperationStatus DecodeFromUtf8InPlace(Span<byte> buffer, out int bytesWritten);

    // Max length APIs
    public static int GetMaxDecodedFromUtf8Length(int length);
    public static int GetMaxEncodedToUtf8Length(int length);

    // IsValid
    public static bool IsValid(ReadOnlySpan<char> base64UrlText);
    public static bool IsValid(ReadOnlySpan<char> base64UrlText, out int decodedLength);
    public static bool IsValid(ReadOnlySpan<byte> base64UrlTextUtf8);
    public static bool IsValid(ReadOnlySpan<byte> base64UrlTextUtf8, out int decodedLength);

    // Up to this point, this is a mirror of System.Buffers.Text.Base64
    // Below are more helpers that bring over functionality similar to Convert.*Base64*

    // Encode to / decode from chars
    public static bool TryEncodeToChars(ReadOnlySpan<byte> bytes, Span<char> chars, out int charsWritten) { }
    public static bool TryDecodeFromChars(ReadOnlySpan<char> chars, Span<byte> bytes, out int bytesWritten) { }


    // These are just accelerator methods.
    // Should be efficiently implementable on top of the other ones in just a few lines.

    // Encode to string
    public static string EncodeToString(ReadOnlySpan<char> chars, Encoding encoding) { }
    public static string EncodeToString(ReadOnlySpan<byte> bytes) { }

    // Decode from chars => string
    // Decode from chars => byte[]
    // The names could also just be "Decode" without naming the return type
    public static string DecodeToString(ReadOnlySpan<char> chars, Encoding encoding) { }
    public static byte[] DecodeToByteArray(ReadOnlySpan<char> chars) { }
}

---

Original issue

The Base64 implementation in System.Memory provides excellent low-level optimizations for RFC 4648, but it currently uses a fixed alphabet. Minor refactoring would add additional use cases using the existing implementation.

Rationale and Usage

The most obvious use case for this change is to support the encoding variant known as Base 64 URL also described in RFC 4648 §4.

This excerpt from the RFC describes the difference between the standard Base 64 alphabet and the Base 64 URL alphabet.

This encoding is technically identical to the previous one, except
for the 62:nd and 63:rd alphabet character...

I have already been able to verify the encoding and decoding in a copy of the current implementation by merely changing the 2 relevant characters in the alphabet mappings at:

• Line 519 in Base64Encoder.cs
• Line 611 in Base64Decoder.cs

Today, this logic is suboptimally implemented in at least:

• Base64UrlTextEncoder.cs (ASP.NET Core)
• WebEncoders.cs (ASP.NET Core)

Furthermore, the encoding is generic and has use cases outside of ASP.NET (e.g. you shouldn't have to reference ASP.NET to use it).

Proposed API Change

The existing Base64.EncodeToUtf8 and Base64.DecodeFromUtf8 should each add a new method overload that allows one of the following:

1. A new enumeration of allowed alphabets (ex: Base64Alphabet) which internally maps to well-known alphabet spans

2. Allow any custom alphabet to be supplied as ReadOnlySpan<sbyte> that must have an exact length of 64 for encoding and 256 for decoding

   a. One or more new types could be provided with static properties for the well-known alphabet spans

Details

Option 1 requires less validation, but has less flexibility. Option 2 has more flexibility, including scenarios not described here, but requires more validation before using the alphabet.

Although the standard Base 64 and Base 64 URL are technically the same encoding with different alphabets, Base 64 URL typically does not include padding. RFC 4648 §3.2 indicates this is allowed (as it's explicitly stated), but there is no need to make that concession in this API. Including the = character for padding in Base 64 URL encoding is still correct.

Both approaches would have a similar looking API:

public static unsafe OperationStatus EncodeToUtf8(
    ReadOnlySpan<byte> bytes,
    Span<byte> utf8,
    Base64Alphabet alphabet,
    out int bytesConsumed,
    out int bytesWritten,
    bool isFinalBlock = true);

public static unsafe OperationStatus DecodeFromUtf8(
    ReadOnlySpan<byte> utf8,
    Span<byte> bytes,
    Base64Alphabet alphabet,
    out int bytesConsumed,
    out int bytesWritten,
    bool isFinalBlock = true);

Figure 1: Supply an alphabet enumeration

public static unsafe OperationStatus EncodeToUtf8(
    ReadOnlySpan<byte> bytes,
    Span<byte> utf8,
    ReadOnlySpan<byte> alphabet,
    out int bytesConsumed,
    out int bytesWritten,
    bool isFinalBlock = true);

public static unsafe OperationStatus DecodeFromUtf8(
    ReadOnlySpan<byte> utf8,
    Span<byte> bytes,
    ReadOnlySpan<byte> alphabet,
    out int bytesConsumed,
    out int bytesWritten,
    bool isFinalBlock = true);

Figure 2: Supply a custom alphabet

The support for trimming off and re-adding padding should be implemented separately. This could be in a separate Base64Url class or, perhaps more appropriately, added as a new type in System.Text.Encodings.Web.

Padding is generally very cheap to deal with compared to other implementation methods. Trimming involves walking the tail end of the span while there are padding characters and then slicing it off. Re-padding fills the end of the span buffer before decoding. Neither operation requires additional allocations.

Open Questions

• Does Option 1 or Option 2 make more sense?
• To complete the cycle, it feels like there should be a type that fully handles the encoding and decoding with trimmed padding. Does that make sense to be in System.Memory, System.Text.Encodings.Web, or perhaps some other place?

[danmoseley]

@GrabYourPitchforks

[GrabYourPitchforks]

What we're considering is no longer base64. It should really be a different API named base64url.

[commonsensesoftware]

@GrabYourPitchforks not exactly - that's merely a canonical name. From an encoding and decoding perspective they are just different alphabets at the lowest level. You literally just exchange 2 characters in the respective encoding and decoding (e.g. 4 numbers). It took me exponentially more time to understand the existing implementation than it did to to make the actual change.

Mostly, I wanted to get the discussion going. There are several ways this proposed change could be implemented. If we split out the API into a new type called Base64Url I think that's more than sufficient. That's actually how I implemented it in my solution. After realizing that this is a common scenario, I thought it would be appropriate to formally discuss supporting it for others to leverage. The method signatures between Base64 and Base64Url would be exactly the same or, at least, they certainly can be.

If we were to take this approach, then it feels like most of the existing Base64 implementation should be refactored into a some other internal type (ex: Base64Core), which can be shared between the two implementations (since they would both be static classes). The internal implementation would then accept the appropriate alphabet leaving the rest of the encoding and decoding algorithm the same.

Thoughts?

[gfoidl]

leaving the rest of the encoding and decoding algorithm the same

This depends how padding is handled (especially for base64Url).

Furthermore the current implementation is vectorized.
base64Url can also be vectorized, but some tricks used for base64 are not applicable for base64url.
That means either two different vectorized implementations, or switch to a less optimized variant so that the code-pathes align (even when vectorized).

The same holds for the option with the user specified alphabet.

[commonsensesoftware]

@gfoidl the padding need not be handled directly in the encoding/decoding, which makes things simpler; the RFC also says as much. I agree, however, that most people will expect the padding to be handled automatically, which is why my original suggestion was to move that responsibility outside of the encoding/decoding process. If we want to include that in the Base64Url class, that's fine by me, but that is merely encapsulating some very basic behavior after encoding and before decoding.

Code is worth a thousand words. I've thrown up the gist of what I'm talking about. I'm well aware that the implementation uses vectors to map the alphabets. Like you, I merely changed the mapping of the alphabet here and here (on this line and this line). I didn't change anything else. I suspect you changed things to make it work with .NET Standard, which is not one of my goals.

In pure terms of implementing the RFC specification, this is functionally correct. I acknowledge that consumers will expect padding to be automatically handled, which is why you can see everything come together in my rendition of Base64Url.cs.

I'm not saying that my implementation should necessarily be the winning design. Step one is to agree that these two things are very, very similar and that it makes sense for the core implementation to not only live together, but that the two have a shared implementation. Exactly which part of API is publicly exposed and what it looks like is wide open for discussion.

The specification implies that there could be alternate alphabets. These are the only two I know of. I'm completely onboard with closing the door on open-ended alphabets. There's no need to over-engineer this. I'm content with saying these are the only two alphabets supported and they are internally mapped. If that somehow ever changes in the future, there seems to be a straight forward path as to how that would be achieved.

[gfoidl]

In general I agree with you.
But I'm afraid perf will suffer when the two implementations are shared -- especially for short to medium inputs, as the overhead for handling padding may be to high. I'm happy if my fear is superfluos.

closing the door on open-ended alphabets

👍
(can you please update the title of this issue)

---

I suspect you changed things to make it work with .NET Standard

I don't know to which change you refer. In the linked project (in my last comment) most changes are for perf, and the vectorized approach -- especially for decoding -- is different for base64 and base64Url.

[commonsensesoftware]

Happy to update the title. What should it say now? "Support Base 64 URL"?

I didn't dissect your implementation, but it clearly looked different and I saw compiler directives. Maybe there's something I don't understand about the encoding and decoding process, which would negate my initial assumptions. My understanding of the specification and the vectorized implementation is as follows:

Encoding

Define the alphabet as a 64 element vector where each element represents the alphabet character. A bunch of optimized techniques and math are then used to calculate which character to use while encoding.

Decoding

Define the decoding map as a 256 (technically only 255 is needed) element vector where each element represents the encoded character which maps back to the corresponding encoding alphabet character. A bunch more optimized techniques and math are used to decode the text.

---

The differences between the encoding and decoding is merely using - and _ instead of + and / at the exact same positions. With the vectors correctly mapped, encoding/decoding should be no different. I've been using this implementation for a while and haven't encountered any tests or scenarios where things didn't encode/decode properly nor result in a difference from other suboptimal methods. However, that doesn't mean I might not be wrong.

I'll reiterate that padding need not be handled directly in the encoding/decoding process (refer to my example). Unless I've completely missed something else, that means the only difference between the encoding/decoding process is alphabet-to-vector map. Conceptually, this feels like this can be handled by refactoring to a parameter or something other method. I recognize these are very low-level APIs and performance sensitive. I defer to bigger brains than mine as to what the best approach is, but seems to me that choosing vector A or B or passing it as a ref parameter is quite cheap.

I re-reviewed your implementation and it seems you are accounting for the padding directly in the encoding/decoding process. That is not what I'm suggesting, but maybe that's a better way to go. In that case, we end up with two distinct encoding/decoding implementations for each alphabet, where the Base 64 URL implementation directly accounts for padding too. The underlying algorithms are quite complex and advanced. My original thinking was that we don't need different algorithms, just different alphabets where padding can be handled outside of the encoding/decoding process for Base 64 URL (the spec even shows = as the pad character in the alphabet). Furthermore, the worst possible scenario in Base 64 is 2 padding characters, which means any pre/post fix-up has seemingly low perf impact (for Base 64 URL only). I'm sure my technique to handle this is suboptimal, but I suspect improvements could be made without having to reimplement the entire algorithm.

I'm onboard to support two different, optimized algorithms if that's the agreed upon approach, it just seems like it's unnecessary maintenance overhead and complexity.

[gfoidl]

"Support Base 64 URL"?

Sounds good.

---

We're going down to implementation details...I think it's too early for this. First there should be a consense about the API design / shape.

Maybe we mismatch "vectorized". When I mean "vectorized" it's SIMD. You mean "array of data" (here a lookup table (LUT)).
The SIMD-versions of base64 and base64Url are different, as the cool tricks there won't map directly to the different alphabet. And the SIMD-version brings a huge perf-win.

For padding: I understood what you suggested 😉 But all users of base64Url (in the .NET landscape) use it without padding (e.g. ASP.NET Core), so this should be handled directly. At leasst with a default param -- so a user could opt-in to keep the padding.

Pure scalar code and w/o padding in mind, you're absolutely right that the implementations are equivalent, just with differnt LUTs. Hence it makes sense to share as much code as possible. As said before, it's heavily optimized so I'm afraid it's not that easy without perf-loss or introducing even more complex code by playing JIT-tricks.

I'll wait for some info from the API designers here.
Personally I don't have any strong preference in either direction. Just want to throw an eye about the perf-thing.

[commonsensesoftware]

Title updated.

Alright ... we are agreed. I guess we enter the holding pattern for stakeholders to decide. I'm personally not married to any code or design, I'd just like to see all of the perf goodness flow from the lowest levels up, which currently isn't happening. 😉