[Tarantool-patches] [PATCH v6 2/2] base64: improve decoder performance

[Alexander Turenko]

On Mon, Jan 11, 2021 at 12:45:01PM +0300, Sergey Nikiforov wrote:
> Unnecessary checks were removed from internal loops.
> Benchmark shows that performance is now ~1.19 times higher
> (release build, Intel Core I7-9700K, only one thread).
> ---
> 
> Branch: https://github.com/tarantool/tarantool/tree/void234/gh-3069-fix-base64-memory-overrun-v6
> 
>  third_party/base64.c | 35 ++++++++++++++++++++++++++---------
>  1 file changed, 26 insertions(+), 9 deletions(-)
> 
> diff --git a/third_party/base64.c b/third_party/base64.c
> index 3ecd0843a..74260971b 100644
> --- a/third_party/base64.c
> +++ b/third_party/base64.c
> @@ -258,10 +258,10 @@ base64_decode_block(const char *in_base64, int in_len,
>  		{
>  	case step_a:
>  			do {
> -				if (in_pos == in_end || out_pos >= out_end)
> +				if (in_pos >= in_end)

Okay, it is the loop invariant and so we can move it outside the loop.
But why we sink it down rather than hoisting up? We know that there is
no space in the output buffer -- so there is no sense to read the input,
right? Or it will break 'correctness' of the hypotetical use of the
`state`?

So we should imagine how the state would be used if it would be
possible. From which input position the processing would be resumed if
the code would provide such ability? How a caller supposed to
distinguish end of the output buffer from successful processing the
whole input?

Aside of this, skipping unrecognized input bytes looks as another
incorrectness. We should be ready to work with untrusted input, perform
appropriate validation and report errors.

We can skip newlines, but I guess there is no sense to do this in a
loop: only one newline is a row is allowed (but it worth to verify the
guess with the standard).

It is hard to discuss an optimization until we'll define how the result
should look in the corner cases like 'short output buffer', 'unexpected
end of an input buffer' and so on. Current code does not report errors:
it silently skips invalid input, accepts trimmed input, silently trims
output at the buffer boundary. I don't understand how it supposed to
work with untrusted input.

I propose to stop attempts to do some 'quick fixups' and either work on
the code or don't.

If we would define behaviour first, I would spend MUCH less time trying
to deduce it.

That's really hard to discuss correctness of dead code. To be honest, it
looks easier to me to finish the chained processing implementation, test
it and remove than rather than trying to interpter the code (both
existing and imaginary) in the mind.

BTW, it seems we able to entirely eliminate the output buffer length
checks for the first (out_len * 3 / 4) input bytes and than process the
tail with full checks. (After we'll done with strict and correct API.)