Performance Bottleneck in jwt::decoded_jwt due to Linear Search

[ItsAMeMarcel]

What would you like to see added?

Lookup Table for base64/bas64url Decoding

Additional Context

Hi folks,

Over the past few days, I’ve been researching performance issues related to jwt-cpp and have noticed a bottleneck in the jwt::decoded_jwt / jwt::alphabet::index functionality. The main cause of this appears to be the use of find_if during Base64 decoding. Since find_if performs a linear search, this results in an O(n) complexity for the decoding process.

In contrast, the encoding process in jwt-cpp uses a lookup table, which operates in O(1), making it significantly faster.

I’d like to suggest two possible ways of improvement:

1. Use OpenSSL’s Base64 implementation (OpenSSL using lookup tables): One challenge with this approach is that OpenSSL doesn’t natively support Base64URL, meaning we’d have to manually preprocess and postprocess the data. This would require caution to avoid modifying user data and introducing unnecessary copying.

2. Implement a reverse lookup table for char-to-index mapping: This would align the decoding process with the encoding by using an O(1) lookup table. One consideration here is the limitation of constexpr in C++11. Also some changes in the internal functions of decode would be needed.

In my opinion, option 2 seems easier to implement.

What are your thoughts about this?