[Tarantool-patches] [PATCH v2 2/2] base64: Improve decoder performance

[Vladislav Shpilevoy]

>> This test now crashes:
>>
>> ====================
>> --- a/test/unit/base64.c
>> +++ b/test/unit/base64.c
>> @@ -7,7 +7,7 @@ static void
>>   base64_test(const char *str, int options, const char *no_symbols,
>>           int no_symbols_len)
>>   {
>> -    plan(3 + no_symbols_len);
>> +    plan(4 + no_symbols_len);
>>         int len = strlen(str);
>>       int base64_buflen = base64_bufsize(len + 1, options);
>> @@ -34,6 +34,11 @@ base64_test(const char *str, int options, const char *no_symbols,
>>       free(base64_buf);
>>       free(strbuf);
>>   +    const char *in = "sIIpHw==";
>> +    int in_len = strlen(in);
>> +    rc = base64_decode(in, in_len, NULL, 0);
>> +    is(rc, 0, "no space in out buffer");
>> +
>>       check_plan();
>>   }
>> ====================
>>
>> It didn't crash while the checks were in place.
> 
> I knew about this "problem" even before first patch version. Glad someone noticed. More on that below.
> 
>> I would suggest to
>> add this test to the previous commit. Because technically it is
>> also 'buffer overrun'. And it will crash 3069 bug even without ASAN.
> 
> I do not think this is a good idea.
> 
> Both old code and your proposed change (below) behave like this: if output buffer size if 0, stop everything and return zero. No input chars are decoded even when this is possible (no "stored" bits in state - aka "step_a" - and only one valid input char with 6 new bits). My "optimized" code already handles such situation properly. And this is "free" (no extra if's).
> 
> It is of course possible to process "zero output buffer size" situation properly but it would require additional "if" in base64_decode_block() beginning and some logic - and in every case except "step_a with no more than one useful input char" would cause some input characters to be lost anyway. Existing API for base64_decode() completely ignores situation when output buffer is too small (it is easy to calculate worst-case output buffer size) - not-yet-processed input data is ignored in such case. No reasonable programmer would use "0" as output buffer size. Such requirement is even DOCUMENTED in base64.h.
> 
> What would you say?

I don't mind leaving it as is. But then I suggest to add an assertion, that
the out-buffer length >= in-buffer length * 3 / 4. If it will crash
anywhere in the tests, it will mean the function is used not only with
the buffers of the given size. And you can't assume it can be not big
enough to fit the whole output, but never 0.

If it will not crash, it means you can drop the out-buffer length
parameter as it does not matter. Also you need to validate all the
usages of base64_decode() just in case.

Talking of DOCUMENTATION - it is for base64_decode(), not for
base64_decode_block(), which you patch. This function does not have
documentation, but clearly it tries not to overflow the out-buffer
somewhy. From its name it seems it can be called multiple times to
decode a buffer step-by-step.

>> For this patch you may want to add a zero length in the beginning.
>> Also we can keep the number of 'if's unchanged like this:
>>
>> ====================
>> --- a/third_party/base64.c
>> +++ b/third_party/base64.c
>> @@ -256,6 +256,12 @@ base64_decode_block(const char *in_base64, int in_len,
>>           while (1)
>>           {
>>       case step_a:
>> +            if (out_pos >= out_end)
>> +            {
>> +                state->step = step_a;
>> +                state->result = curr_byte;
>> +                return out_pos - out_bin;
>> +            }
>>               do {
>>                   if (in_pos >= in_end)
>>                   {
>> @@ -316,12 +322,7 @@ base64_decode_block(const char *in_base64, int in_len,
>>               } while (fragment < 0);
>>               curr_byte |= (fragment & 0x03f);
>>               *out_pos = curr_byte;
>> -            if (++out_pos >= out_end)
>> -            {
>> -                state->step = step_a;
>> -                state->result = curr_byte;
>> -                return out_pos - out_bin;
>> -            }
>> +            ++out_pos;
>>           }
>>       }
>>       /* control should not reach here */
>> ====================
>>
>> Will that work?
> 
> Yes, but it would lose data when (out_len == 0), (state->step == step_a) and there is one useful char in input buffer. Not that it matter in real life.

This can be fixed, nothing scary here.