barrel_encoding

%% -*- erlang -*-
%%%
%%% This file is part of barrel_encoding released under the Apache 2 license.
%%% See the NOTICE for more information.
%%%
%%% Copyright (c) 2018-2019 Benoît Chesneau <bchesneau@pm.me>

-module(barrel_encoding).

-export([encode_uint32_ascending/2, encode_uint32_descending/2,
         decode_uint32_ascending/1, decode_uint32_descending/1,
         encode_uint64_ascending/2, encode_uint64_descending/2,
         decode_uint64_ascending/1, decode_uint64_descending/1,
         encode_varint_ascending/2, encode_varint_descending/2,
         decode_varint_ascending/1, decode_varint_descending/1,
         encode_uvarint_ascending/2, encode_uvarint_descending/2,
         decode_uvarint_ascending/1, decode_uvarint_descending/1,
         encode_binary_ascending/2, encode_binary_descending/2,
         decode_binary_ascending/1, decode_binary_descending/1,
         encode_literal_ascending/2, decode_literal_ascending/1,
         encode_literal_descending/2, decode_literal_descending/1,
         encode_nonsorting_uvarint/2,
         decode_nonsorting_uvarint/1,
         encode_float_ascending/2, encode_float_descending/2,
         decode_float_ascending/1, decode_float_descending/1]).

%% JSON encoding
-export([
  encode_json_empty_array/1,
  encode_json_empty_object/1,
  encode_json_key_ascending/3,
  encode_array_ascending/2,
  encode_array_index_ascending/3,
  encode_array_ascending/1,
  add_json_path_terminator/1,
  encode_json_ascending/1
]).

-export([pick_encoding/1]).

-include("barrel_encoding.hrl").

pick_encoding(<< ?BYTES_MARKER, _/binary >>) -> bytes;
pick_encoding(<< ?BYTES_MARKER_DESC, _/binary >>) -> bytes_desc;
pick_encoding(<< ?LITERAL_MARKER, _/binary >>) -> literal;
pick_encoding(<< ?LITERAL_MARKER_DESC, _/binary >>) -> literal_desc;
pick_encoding(<< M, _/binary >>) when M >= ?INT_MIN, M =< ?INT_MAX -> int;
pick_encoding(<< M, _/binary >>) when M >= ?FLOAT_NAN, M =< ?FLOAT_NAN_DESC -> float;
pick_encoding(_) -> erlang:error(badarg).

%% @doc  encodes the uint32 value using a big-endian 8 byte representation.
%% The bytes are appended to the supplied buffer and the final buffer is returned.
encode_uint32_ascending(B, V) when is_binary(B), is_integer(V), V >= 0 ->
  << B/binary, V:32/big-integer >>;
encode_uint32_ascending(B, V) when is_binary(B), is_integer(V) ->
  << N:32/native-unsigned >> = << V:32/signed-native >>,
  << B/binary, N:32/big-integer >>;
encode_uint32_ascending(_, _) ->
  erlang:error(badarg).

%% @doc encodes the uint32 value so that it sorts in reverse order, from largest to smallest.
encode_uint32_descending(B, V) when is_integer(V) ->
  encode_uint32_ascending(B, bnot V);
encode_uint32_descending(_, _) ->
  erlang:error(badarg).

%% @doc decodes a uint32 from the input buffer, treating
%% the input as a big-endian 4 byte uint32 representation. The remainder
%% of the input buffer and the decoded uint32 are returned.
decode_uint32_ascending(<< V:32/big-integer, B/binary >>) -> {to_uint32(V), B};
decode_uint32_ascending(_B) -> erlang:error(badarg).

%% @doc decodes a uint32 value which was encoded using `encode_uint32_descending/2'.
decode_uint32_descending(B) ->
  {V, LeftOver} = decode_uint32_ascending(B),
  {to_uint32(bnot V), LeftOver}.


to_uint32(N) ->
  Mask = (1 bsl 32) - 1,
  N band Mask.

%% @doc encodes the uint64 value using a big-endian 8 byte representation.
%% The bytes are appended to the supplied buffer and  the final buffer is returned.
encode_uint64_ascending(B, V) when V >= 0 ->
  << B/binary, V:64/big-integer >>;
encode_uint64_ascending(B, V)  ->
  << N:64/native-unsigned >> = << V:64/signed-native >>,
  << B/binary, N:64/big-integer >>.

%% @doc encodes the uint64 value so that it sorts in  reverse order,
%% from largest to smallest.
encode_uint64_descending(B, V) when is_integer(V) ->
  encode_uint64_ascending(B, bnot V);
encode_uint64_descending(_, _) ->
  erlang:error(badarg).

%% @doc decodes a uint64 from the input buffer, treating
%% the input as a big-endian 8 byte uint64 representation. The remainder
%% of the input buffer and the decoded uint64 are returned.
decode_uint64_ascending(<< V:64/big-integer, B/binary >>) -> {to_uint64(V), B};
decode_uint64_ascending(_B) -> erlang:error(badarg).

%% @doc D decodes a uint64 value which was encoded using `encode_uint_64_descending/2'.
decode_uint64_descending(B) ->
  {V, LeftOver} = decode_uint64_ascending(B),
  {to_uint64(bnot V), LeftOver}.

to_uint64(N) ->
  Mask = (1 bsl 64) - 1,
  N band Mask.


%% @doc EncodeVarintAscending encodes the int64 value using a variable length
%% (length-prefixed) representation. The length is encoded as a single
%% byte. If the value to be encoded is negative the length is encoded
%% as 8-numBytes. If the value is positive it is encoded as
%% 8+num_bytes. The encoded bytes are appended to the supplied buffer
%% and the final buffer is returned.
encode_varint_ascending(B, V) when V < 0 ->
  encode_varint_ascending_1(B, V);
encode_varint_ascending(B, V) ->
  encode_uvarint_ascending(B, to_uint64(V)).


encode_varint_ascending_1(B, V) when V >= -16#ff ->
  << B/binary, (?INT_MIN + 7), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffff ->
  << B/binary, (?INT_MIN + 6), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffffff ->
  << B/binary, (?INT_MIN + 5), (V bsr 16), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffffffff ->
  << B/binary, (?INT_MIN + 4), (V bsr 24), (V bsr 16), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffffffffff ->
  << B/binary, (?INT_MIN + 3), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffffffffffff ->
  << B/binary, (?INT_MIN + 2), (V bsr 40), (V bsr 32), (V bsr 24), (V bsr 16), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) when V >= -16#ffffffffffffff ->
  << B/binary, (?INT_MIN + 1), (V bsr 48), (V bsr 40), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>;
encode_varint_ascending_1(B, V) ->
  << B/binary, ?INT_MIN, (V bsr 56), (V bsr 48), (V bsr 40), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>.



%% @doc EncodeVarintDescending encodes the int64 value so that it sorts in reverse
%% order, from largest to smallest.
encode_varint_descending(B, V)  ->
  encode_varint_ascending(B, bnot V).


%% @doc decodes a value encoded by `encode_varint_ascending/2'.
decode_varint_ascending(<<>>) -> erlang:error(badarg);
decode_varint_ascending(<< L, _/binary >> = B) ->
  Length = L - ?INT_ZERO,
  decode_varint_ascending_1(B, Length, -Length).


decode_varint_ascending_1(<< _L, B/binary >>, Len, Len2) when Len < 0, byte_size(B) < Len2 ->
  erlang:error(badarg);
decode_varint_ascending_1(<< _L, B0/binary >>, Len, Len2) when Len < 0 ->
  << B1:Len2/binary, LeftOver/binary >> = B0,
  V = fold_binary(B1,
                  fun(T, V1) ->
                      V2 = (V1 bsl 8)  bor (bnot T) band 16#ff,
                      V2
                  end,
                  0),
  {bnot V, LeftOver};
decode_varint_ascending_1(B, _Len, _Len2) ->
  {V, LeftOver} = decode_uvarint_ascending(B),
  {to_uint64(V), LeftOver}.

%% @doc decodes a value encoded by encode_varint_ascending
decode_varint_descending(B) ->
  {V, LeftOver} = decode_varint_ascending(B),
  {bnot V, LeftOver}.



%% @doc EncodeUvarintAscending encodes the uint64 value using a variable length
%% (length-prefixed) representation. The length is encoded as a single
%% byte indicating the number of encoded bytes (-8) to follow. See
%% `encode_varint_ascending/2' for rationale. The encoded bytes are appended to the
%% supplied buffer and the final buffer is returned.-
-spec encode_uvarint_ascending(B, V) -> B2 when
    B :: binary(),
    V :: integer(),
    B2 :: binary().
encode_uvarint_ascending(B, V) when V =< ?INT_SMALL ->
  << B/binary, (?INT_ZERO + V) >>;
encode_uvarint_ascending(B, V) when V =< 16#ff ->
  << B/binary, (?INT_MAX - 7), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffff ->
  << B/binary, (?INT_MAX - 6), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffffff ->
  << B/binary, (?INT_MAX - 5), (V bsr 16), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffffffff ->
  << B/binary, (?INT_MAX - 4), (V bsr 24), (V bsr 16), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffffffffff ->
  << B/binary, (?INT_MAX - 3), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffffffffffff ->
  << B/binary, (?INT_MAX - 2), (V bsr 40), (V bsr 32), (V bsr 24), (V bsr 16), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) when V =< 16#ffffffffffffff ->
  << B/binary, (?INT_MAX - 1), (V bsr 48), (V bsr 40), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>;
encode_uvarint_ascending(B, V) ->
  << B/binary, ?INT_MAX, (V bsr 56), (V bsr 48), (V bsr 40), (V bsr 32), (V bsr 24),  (V bsr 16), (V bsr 8), V >>.


encode_uvarint_descending(B, 0) ->
  << B/binary, (?INT_MIN + 8) >>;
encode_uvarint_descending(B, V) when V =< 16#ff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 7), V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffff  ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 6), (V1 bsr 8),  V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffffff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 5), (V1 bsr 16), (V1 bsr 8), V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffffff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 4), (V1 bsr 24), (V1 bsr 16), (V1 bsr 8), V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffffffff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 3), (V1 bsr 32), (V1 bsr 24), (V1 bsr 16), (V1 bsr 8), V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffffffffff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 2), (V1 bsr 40), (V1 bsr 32), (V1 bsr 24), (V1 bsr 16), (V1 bsr 8), V1 >>;
encode_uvarint_descending(B, V) when V =< 16#ffffffffffff ->
  V1 = to_uint64(bnot V),
  << B/binary, (?INT_MIN + 1), (V1 bsr 48), (V1 bsr 40), (V1 bsr 32), (V1 bsr 24), (V1 bsr 16), (V1 bsr 8), V1 >>;
encode_uvarint_descending(B, V) ->
  V1 = bnot V,
  << B/binary, ?INT_MIN, (V1 bsr 56), (V1 bsr 48), (V1 bsr 40), (V1 bsr 32), (V1 bsr 24),
    (V1 bsr 16), (V1 bsr 8), V1 >>.


decode_uvarint_ascending(<<>>) -> erlang:error(badarg);
decode_uvarint_ascending(<< B_0, B/binary >>) ->
  Len = B_0 - ?INT_ZERO,
  decode_uvarint_ascending_1(B, Len, Len - ?INT_SMALL).

decode_uvarint_ascending_1(B, Len, _Len2) when Len =< ?INT_SMALL ->
  {to_uint64(Len), B};
decode_uvarint_ascending_1(_B, _Len, Len2) when Len2 < 0; Len2 > 8 ->
  erlang:error(badarg);
decode_uvarint_ascending_1(B, _Len, Len2) when byte_size(B) < Len2 ->
  erlang:error(badarg);
decode_uvarint_ascending_1(B0, _Len, Len2) ->
  << B1:Len2/binary, LeftOver/binary >> = B0,
  V = fold_binary(B1,
                  fun(T, V1) ->
                      V2 = (V1 bsl 8) bor to_uint64(T),
                      V2
                  end,
                  0),
  {V, LeftOver}.


decode_uvarint_descending(<<>>) ->
  erlang:error(badarg);
decode_uvarint_descending(<< B_0, B/binary >>) ->
  Len = ?INT_ZERO - B_0,
  decode_uvarint_descending_1(B, Len).

decode_uvarint_descending_1(_B, Len) when Len < 0; Len > 8 ->
  erlang:error(badarg);
decode_uvarint_descending_1(B, Len) when byte_size(B) < Len ->
  erlang:error(badarg);
decode_uvarint_descending_1(B0, Len) ->
  << B1:Len/binary, LeftOver/binary >> = B0,
  V = fold_binary(B1,
                  fun(T, V1) ->
                      V2 = (V1 bsl 8) bor (to_uint64(bnot T band 16#ff)),
                      V2
                  end,
                 0),
  {V, LeftOver}.

fold_binary(<< C, Rest/binary >>, Fun, Acc) -> fold_binary(Rest, Fun, Fun(C, Acc));
fold_binary(<<>>, _Fun, Acc) -> Acc.


encode_binary_ascending(B, Bin) ->
  Bin2 = binary:replace(Bin, << ?ESCAPE >>, << ?ESCAPE, ?ESCAPED_00 >>, [global]),
  << B/binary, ?BYTES_MARKER, Bin2/binary, ?ESCAPE, ?ESCAPED_TERM >>.

encode_binary_descending(B, Bin) ->
  Bin2 = inverse(
           << (binary:replace(Bin, << ?ESCAPE >>, << ?ESCAPE, ?ESCAPED_00 >>, [global]))/binary,
               ?ESCAPE, ?ESCAPED_TERM >>
          ),
  << B/binary, ?BYTES_MARKER_DESC, Bin2/binary >>.

decode_binary_ascending(<< ?BYTES_MARKER, B/binary >>) ->
  case binary:split(B, << ?ESCAPE, ?ESCAPED_TERM >>) of
    [Bin, LeftOver] -> {binary:replace(Bin, << ?ESCAPE, ?ESCAPED_00 >>, << ?ESCAPE >>, [global]), LeftOver};
    _ -> erlang:error(badarg)
  end;
decode_binary_ascending(_) ->
  erlang:error(badarg).

decode_binary_descending(<< ?BYTES_MARKER_DESC, B/binary >>) ->
  case binary:split(B, inverse(<< ?ESCAPE, ?ESCAPED_TERM >>)) of
    [Bin, LeftOver] ->
      Bin2 = binary:replace(
               inverse(Bin),
               << ?ESCAPE, ?ESCAPED_00 >>,
               << ?ESCAPE >>,
               [global]
              ),
      {Bin2, LeftOver};
    _ ->
      erlang:error(badarg)
  end;
decode_binary_descending(_) ->
  erlang:error(badarg).


inverse(B1) ->
  S = bit_size(B1),
  <<V1:S>> = B1,
  V2 = bnot V1,
  <<V2:S>>.

encode_literal_ascending(B, L) ->
  ok = is_literal(L),
  << B/binary, ?LITERAL_MARKER, (atom_to_binary(L, latin1))/binary, ?ESCAPE, ?ESCAPED_TERM >>.

encode_literal_descending(B, L) ->
  ok = is_literal(L),
  Bin2 = inverse(<< (atom_to_binary(L, latin1))/binary, ?ESCAPE, ?ESCAPED_TERM >>),
  << B/binary, ?LITERAL_MARKER_DESC, Bin2/binary >>.

is_literal(true) -> ok;
is_literal(false) -> ok;
is_literal(null) -> ok;
is_literal(_) -> erlang:error(badarg).

decode_literal_ascending(<< ?LITERAL_MARKER, B/binary >>) ->
  case binary:split(B, << ?ESCAPE, ?ESCAPED_TERM >>) of
    [Bin, LeftOver] -> {binary_to_atom(Bin, latin1), LeftOver};
    _ -> erlang:error(badarg)
  end;
decode_literal_ascending(_) ->
  erlang:error(badarg).

decode_literal_descending(<< ?LITERAL_MARKER_DESC, B/binary >>) ->
  case binary:split(B, inverse(<< ?ESCAPE, ?ESCAPED_TERM >>)) of
    [Bin, LeftOver] ->
      {binary_to_atom(inverse(Bin), latin1), LeftOver};
    _ ->
      erlang:error(badarg)
  end.



%% @doc encodes a uint64, appends it to the supplied buffer,
%% and returns the final buffer. The encoding used is similar to
%% encoding/binary, but with the most significant bits first
%% - Unsigned integers are serialized 7 bits at a time, starting with the
%% most significant bits.
%% - The most significant bit (msb) in each output byte indicates if there
%% is a continuation byte (msb = 1).
encode_nonsorting_uvarint(B, X) when X < (1 bsl 7) ->
  << B/binary, X >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 14) ->
  << B/binary, (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 21) ->
  << B/binary, (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 28) ->
  << B/binary, (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 35) ->
  << B/binary, (16#80 bor (X bsr 28)), (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)),
     (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 42) ->
  << B/binary, (16#80 bor (X bsr 35)), (16#80 bor (X bsr 28)), (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)),
     (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 49) ->
  << B/binary, (16#80 bor (X bsr 42)), (16#80 bor (X bsr 35)), (16#80 bor (X bsr 28)), (16#80 bor (X bsr 21)),
     (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 56) ->
  << B/binary, (16#80 bor (X bsr 49)), (16#80 bor (X bsr 42)), (16#80 bor (X bsr 35)), (16#80 bor (X bsr 28)),
     (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) when X < (1 bsl 63) ->
  << B/binary, (16#80 bor (X bsr 56)), (16#80 bor (X bsr 49)), (16#80 bor (X bsr 42)), (16#80 bor (X bsr 35)),
     (16#80 bor (X bsr 28)), (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)), (16#80 bor (X bsr 7)), (16#7f band X) >>;
encode_nonsorting_uvarint(B, X) ->
  << B/binary, (16#80 bor (X bsr 63)), (16#80 bor (X bsr 56)), (16#80 bor (X bsr 49)), (16#80 bor (X bsr 42)),
     (16#80 bor (X bsr 35)), (16#80 bor (X bsr 28)), (16#80 bor (X bsr 21)), (16#80 bor (X bsr 14)),
     (16#80 bor (X bsr 7)), (16#7f band X) >>.


%% @doc decodes a value encoded by `encode_nonsorting_uvarint/2'. It
%% returns the length of the encoded varint and value.
decode_nonsorting_uvarint(B) ->
  decode_nonsorting_uvarint(B, 0).

decode_nonsorting_uvarint(<< C, Rest/binary >>, V0) when C < 16#80 ->
  V1 = V0 bsl 7 + to_uint64(C band 16#7f),
  {V1, Rest};
decode_nonsorting_uvarint(<< C, Rest/binary >>, V0) ->
  V1 = V0 bsl 7 + to_uint64(C band 16#7f),
  decode_nonsorting_uvarint(Rest, V1);
decode_nonsorting_uvarint(<<>>, _) ->
  {0, <<>>}.



encode_float_ascending(B, nan) ->
  << B/binary, ?FLOAT_NAN >>;
encode_float_ascending(B, F) ->
  << Sign:1, _:11, _:52 >> = BinF = << F/float >>,
  U = binary:decode_unsigned(BinF),
  encode_float_ascending(Sign, U, B).

encode_float_ascending(_, 0, B) ->
  << B/binary, ?FLOAT_ZERO >>;
encode_float_ascending(0, U, B) ->
  encode_uint64_ascending(<< B/binary, ?FLOAT_POS >>, U);
encode_float_ascending(1, U, B) ->
  encode_uint64_ascending(<< B/binary, ?FLOAT_NEG >>, bnot U ).

encode_float_descending(B, nan) ->
  << B/binary, ?FLOAT_NAN_DESC >>;
encode_float_descending(B, F) ->
  encode_float_ascending(B, -F).

decode_float_ascending(<< ?FLOAT_NAN, B/binary >>) -> {nan, B};
decode_float_ascending(<< ?FLOAT_NAN_DESC, B/binary >>) -> {nan, B};
decode_float_ascending(<< ?FLOAT_ZERO, B/binary >>) -> {0, B};
decode_float_ascending(<< ?FLOAT_NEG, B/binary >>) ->
  {U, LeftOver} = decode_uint64_ascending(B),
  << F/float >> = binary:encode_unsigned(to_uint64(bnot U)),
  {F, LeftOver};
decode_float_ascending(<< ?FLOAT_POS, B/binary >>) ->
  {U, LeftOver} = decode_uint64_ascending(B),
  << F/float >> = binary:encode_unsigned(U),
  {F, LeftOver};
decode_float_ascending(_) ->
  erlang:error(badarg).

decode_float_descending(B) ->
  {F, LeftOver} = decode_float_ascending(B),
  {-F, LeftOver}.


%% @doc returns a binary with a byte to signify an empty JSON object.
encode_json_empty_object(B) ->
  << B/binary, ?ESCAPE, ?ESCAPED_TERM, ?JSON_EMPTY_OBJECT >>.

%% @doc returns a binary b with a byte to signify an empty JSON array.
encode_json_empty_array(B) ->
  << B/binary, ?ESCAPE, ?ESCAPED_TERM, ?JSON_EMPTY_ARRAY >>.

%%  adds a json path terminator to a binary
add_json_path_terminator(B) ->
  << B/binary, ?ESCAPE, ?ESCAPED_TERM >>.

%% @doc ncodes the JSON key string value with a JSON specific escaped
%% terminator. This allows us to encode keys in the same number of bytes as a string,
%% while at the same time giving us a sentinel to identify JSON keys. The end parameter is used
%% to determine if this is the last key in a a JSON path. If it is we don't add a separator after it.
encode_json_key_ascending(B, Key, true) ->
  encode_binary_ascending(B, Key);
encode_json_key_ascending(B, Key, false) ->
  << (encode_binary_ascending(B, Key))/binary, ?ESCAPED_JSON_OBJECT_KEY_TERM >>.

%% @doc encodes a value used to signify membership of an array for JSON objects.
encode_array_ascending(B) ->
  << B/binary, ?ESCAPE, ?ESCAPED_JSON_ARRAY>>.

encode_array_ascending(B, I) ->
  <<  (encode_uvarint_ascending(B, I))/binary, ?ESCAPE, ?ESCAPED_JSON_ARRAY>>.

%% @doc encodes a value used to signify membership of an array for JSON objects.
encode_array_index_ascending(B, I, true) ->
  encode_uvarint_ascending(B, I);
encode_array_index_ascending(B, I, false) ->
  << (encode_uvarint_ascending(B, I))/binary, ?ESCAPED_JSON_ARRAY_KEY>>.


%% @doc encodes a JSON Type. The encoded bytes are appended to the
%% supplied binary and the final binary is returned.
encode_json_ascending(B) ->
  << B/binary, ?JSON_INVERTED_INDEX >>.

-ifdef(TEST).
-include_lib("eunit/include/eunit.hrl").

encode_uint32_ascending_test() ->
  Tests = [{ << 0, 0, 0, 0 >>, 0 },
           { << 0, 0, 0, 1 >>, 1 },
           { << 0, 0, 1, 0 >>, 1 bsl 8 },
           { << 16#ff, 16#ff, 16#ff, 16#ff >>, 1 bsl 32 - 1 }], %% max uint32
  test_encode_decode(Tests, fun encode_uint32_ascending/2, fun decode_uint32_ascending /1).

encode_uint32_descending_test() ->
  Tests = [{ << 16#ff, 16#ff, 16#ff, 16#ff >>, 0 },
           { << 16#ff, 16#ff, 16#ff, 16#fe >>, 1 },
           { << 16#ff, 16#ff, 16#fe, 16#ff >>, 1 bsl 8 },
           { << 0, 0, 0, 0 >>, 1 bsl 32 - 1 }], %% max uint32
  test_encode_decode(Tests, fun encode_uint32_descending/2, fun decode_uint32_descending/1).


encode_uint64_ascending_test() ->
  Tests = [{ << 0, 0, 0, 0, 0, 0, 0, 0 >>, 0 },
           { << 0, 0, 0, 0, 0, 0, 0, 1 >>, 1 },
           { << 0, 0, 0, 0, 0, 0, 1, 0 >>, 1 bsl 8 },
           { << 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, 1 bsl 64 - 1 }], %% max uint64
  test_encode_decode(Tests, fun encode_uint64_ascending/2, fun decode_uint64_ascending/1).

encode_uint64_descending_test() ->
  Tests = [{ << 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, 0 },
           { << 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff , 16#fe >>, 1 },
           { << 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#fe, 16#ff >>, 1 bsl 8 },
           { << 0, 0, 0, 0, 0, 0, 0, 0 >>, 1 bsl 64 - 1 }], %% max uint 64
  test_encode_decode(Tests, fun encode_uint64_descending/2, fun decode_uint64_descending/1).


encode_varint_ascending_test() ->
  Tests = [{ << 16#86, 16#ff, 16#00 >>, -1 bsl 8 },
           { << 16#87, 16#ff >>, -1 },
           { << 16#88 >>, 0 },
           { << 16#89 >>, 1 },
           { << 16#f5 >>, 109 },
           { << 16#f6, 16#f70 >>, 112 },
           { << 16#f7, 16#01, 16#00 >>, 1 bsl 8 },
           { << 16#fd, 16#7f, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, 16#7FFFFFFFFFFFFFFF}], %% max int64
  test_encode_decode(Tests, fun encode_varint_ascending/2, fun decode_varint_ascending/1).

encode_varint_descending_test() ->
  Tests = [{ << 16#fd, 16#7f, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, -(16#7FFFFFFFFFFFFFFF + 1) }, %% min int64
           { << 16#fd, 16#7f, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#fe >>, -(16#7FFFFFFFFFFFFFFF + 1) + 1 },
           { << 16#f6, 16#ff >>, -1 bsl 8 },
           { << 16#f5 >>, -110 },
           { << 16#87, 16#ff >>, 0 },
           { << 16#87, 16#fe >>, 1 },
           { << 16#86, 16#fe, 16#ff >>, 1 bsl 8 },
           { << 16#80, 16#80, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 16#7FFFFFFFFFFFFFFF }],
  test_encode_decode(Tests, fun encode_varint_descending/2, fun decode_varint_descending/1).

encode_uvarint_ascending_test() ->
  Tests = [{ << 16#88 >>, 0 },
           { << 16#89 >>, 1 },
           { << 16#f5 >>, 109 },
           { << 16#f6, 16#6e >>, 110 },
           { << 16#f7, 16#01, 16#00 >>, 1 bsl 8 },
           { << 16#fd, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, 1 bsl 64 - 1 }],
  test_encode_decode(Tests, fun encode_uvarint_ascending/2, fun decode_uvarint_ascending/1).

encode_uvarint_descending_test() ->
  Tests = [{ << 16#88 >>, 0 },
           { << 16#87, 16#fe >>, 1 },
           { << 16#86, 16#fe, 16#ff >>, 1 bsl 8 },
           { << 16#80, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00, 16#01 >>, (1 bsl 64 - 1) - 1 },
           { << 16#80, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 1 bsl 64 - 1 }],
  test_encode_decode(Tests, fun encode_uvarint_descending/2, fun decode_uvarint_descending/1).

encode_binary_ascending_test() ->
  Tests = [{ << 16#12, 16#00, 16#ff, 1, "a", 16#00, 16#01 >>, << 0, 1, "a" >> },
           { << 16#12, 16#00, 16#ff, "a", 16#00, 16#01 >>, << 0, "a" >> },
           { << 16#12, "a", 16#00, 16#01 >>, <<"a">> },
           { << 16#12, "b", 16#00, 16#01 >>, <<"b">> },
           { << 16#12, "b", 16#00, 16#ff, 16#00, 16#01 >>, <<"b", 0 >> },
           { << 16#12, "b", 16#00, 16#ff, 16#00, 16#ff, 16#00, 16#01 >>, <<"b", 0, 0 >> },
           { << 16#12, "b", 16#00, 16#ff, 16#00, 16#ff, "a", 16#00, 16#01 >>, <<"b", 0, 0, "a" >> },
           { << 16#12, "b", 16#ff, 16#00, 16#01 >>, <<"b", 16#ff >> },
           { << 16#12, $h, $e, $l, $l, $o, 16#00, 16#01 >>, <<"hello">> },
           { << 16#12, "hello", 16#00, 16#01 >>, <<"hello">> }],
  test_encode_decode(Tests, fun encode_binary_ascending/2, fun decode_binary_ascending/1).

encode_binary_descending_test() ->
  Tests = [{ << 16#13, (bnot $h), (bnot $e), (bnot $l), (bnot $l), (bnot $o), 16#ff, 16#fe >>, <<"hello">> },
           { << 16#13, (bnot $b), 16#00, 16#ff, 16#fe >>, << "b", 16#ff >> },
           { << 16#13, (bnot $b), 16#ff, 16#00, 16#ff, 16#00, (bnot $a), 16#ff, 16#fe >>, << "b", 0, 0, "a" >> },
           { << 16#13, (bnot $b), 16#ff, 16#00, 16#ff, 16#00, 16#ff, 16#fe >>, << "b", 0, 0 >> },
           { << 16#13, (bnot $b), 16#ff, 16#00, 16#ff, 16#fe >>, << "b", 0 >> },
           { << 16#13, (bnot $b),  16#ff, 16#fe >>, << "b" >> },
           { << 16#13, (bnot $a),  16#ff, 16#fe >>, << "a" >> },
           { << 16#13, 16#ff, 16#00, 16#00, (bnot $a),  16#ff, 16#fe >>, << 0, 16#ff, "a" >> },
           { << 16#13, 16#ff, 16#00, (bnot $a),  16#ff, 16#fe >>, << 0, "a" >> },
           { << 16#13, 16#ff, 16#00, 16#fe, (bnot $a),  16#ff, 16#fe >>, << 0, 1, "a" >> }],
 test_encode_decode(Tests, fun encode_binary_descending/2, fun decode_binary_descending/1).


encode_literal_ascending_test() ->
  Tests = [{ << 16#14, 16#66, 16#61, 16#6c, 16#73, 16#65, 16#00, 16#01 >>, false },
           { << 16#14, 16#6e, 16#75, 16#6c, 16#6c, 16#00, 16#01 >>, null },
           { << 16#14, 16#74, 16#72, 16#75, 16#65, 16#00, 16#01 >>, true } ],
  test_encode_decode(Tests, fun encode_literal_ascending/2, fun decode_literal_ascending/1).

encode_literal_descending_test() ->
  Tests = [{ << 16#15, (bnot 16#66), (bnot 16#61), (bnot 16#6c), (bnot 16#73), (bnot 16#65), 16#ff, 16#fe >>, false },
           { << 16#15, (bnot 16#6e), (bnot 16#75), (bnot 16#6c), (bnot 16#6c), 16#ff, 16#fe >>, null },
           { << 16#15, (bnot 16#74), (bnot 16#72), (bnot 16#75), (bnot 16#65), 16#ff, 16#fe >>, true } ],
  test_encode_decode(Tests, fun encode_literal_descending/2, fun decode_literal_descending/1).

encode_nonsorting_uvarint_test() ->
  TestEncodeFun = fun(I) ->
                      {I, <<>>} = decode_nonsorting_uvarint(encode_nonsorting_uvarint(<<>>, I)),
                      true
                  end,
  _ = lists:map(TestEncodeFun, edge_case_uint64()),
  _ = lists:map(TestEncodeFun, rand_pow_distributed_int63(1000)).

encode_float_ascending_test() ->
  Tests = [{ << 16#03, 16#00, 16#1e, 16#33, 16#0c, 16#7a, 16#14, 16#37, 16#5f >>, -1.0e308 },
           { << 16#03, 16#3f, 16#3c, 16#77, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, -10000.0 },
           { << 16#03, 16#3f, 16#3c, 16#78, 16#7f, 16#ff, 16#ff, 16#ff, 16#ff >>, -9999.0 },
           { << 16#03, 16#3F, 16#a6, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, -100.0 },
           { << 16#03, 16#40, 16#0f, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff, 16#ff >>, -1.0 },
           { << 16#03, 16#40, 16#ab, 16#d9, 16#01, 16#8e, 16#75, 16#79, 16#28 >>, -0.00123 },
           { << 16#04 >>, 0 },
           { << 16#05, 16#3f, 16#54, 16#26, 16#fe, 16#71, 16#8a, 16#86, 16#d7 >>, 0.00123 },
           { << 16#05, 16#3f, 16#89, 16#30, 16#be, 16#0d, 16#ed, 16#28, 16#8d >>, 0.0123 },
           { << 16#05, 16#3f, 16#bf, 16#7c, 16#ed, 16#91, 16#68, 16#72, 16#b0 >>, 0.123 },
           { << 16#05, 16#3f, 16#f0, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 1.0 },
           { << 16#05, 16#40, 16#24, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 10.0 },
           { << 16#05, 16#40, 16#28, 16#b0, 16#a3, 16#d7, 16#0a, 16#3d, 16#71 >>, 12.345 },
           { << 16#05, 16#40, 16#58, 16#c0, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 99.0 },
           { << 16#05, 16#40, 16#58, 16#c0, 16#01, 16#a3, 16#6e, 16#2e, 16#b2 >>, 99.0001 },
           { << 16#05, 16#40, 16#58, 16#c0, 16#a3, 16#d7, 16#0a, 16#3d, 16#71 >>, 99.01 },
           { << 16#05, 16#40, 16#59, 16#00, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 100.0 },
           { << 16#05, 16#40, 16#59, 16#00, 16#a3, 16#d7, 16#0a, 16#3d, 16#71 >>, 100.01 },
           { << 16#05, 16#40, 16#59, 16#06, 16#66, 16#66, 16#66, 16#66, 16#66 >>, 100.1 },
           { << 16#05, 16#40, 16#93, 16#48, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 1234.0 },
           { << 16#05, 16#40, 16#93, 16#4a, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 1234.5 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#00, 16#00, 16#00, 16#00 >>, 9999.0 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#00, 16#08, 16#63, 16#7c >>, 9999.000001 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#00, 16#4b, 16#7f, 16#5a >>, 9999.000009 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#00, 16#53, 16#e2, 16#d6 >>, 9999.00001 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#02, 16#f2, 16#f9, 16#87 >>, 9999.00009 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#03, 16#3e, 16#78, 16#e2 >>, 9999.000099 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#03, 16#46, 16#dc, 16#5d >>, 9999.0001 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#80, 16#20, 16#c4, 16#9b, 16#a6 >>, 9999.001 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#81, 16#47, 16#ae, 16#14, 16#7b >>, 9999.01 },
           { << 16#05, 16#40, 16#c3, 16#87, 16#8c, 16#cc, 16#cc, 16#cc, 16#cd >>, 9999.1 },
           { << 16#05, 16#40, 16#c3, 16#88, 16#00, 16#00, 16#00, 16#00, 16#00 >>, 10000.0 },
           { << 16#05, 16#40, 16#c3, 16#88, 16#80, 16#00, 16#00, 16#00, 16#00 >>, 10001.0 },
           { << 16#05, 16#40, 16#c8, 16#1c, 16#80, 16#00, 16#00, 16#00, 16#00 >>, 12345.0 },
           { << 16#05, 16#40, 16#fe, 16#23, 16#a0, 16#00, 16#00, 16#00, 16#00 >>, 123450.0 },
           { << 16#05, 16#7f, 16#e1, 16#cc, 16#f3, 16#85, 16#eb, 16#c8, 16#a0 >>, 1.0e308 }],
  test_encode_decode(Tests, fun encode_float_ascending/2, fun decode_float_ascending/1),

  %% test ascending order
  lists:foldl(fun
                ({_Encoded, Value}, nil) ->
                  encode_float_ascending(<<>>, Value);
                ({_Encoded, Value}, Last) ->
                  New = encode_float_ascending(<<>>, Value),
                  true = (New > Last),
                  New
              end,
              nil,
              Tests),

  %% test appending work
  true = (encode_float_ascending(<<"hello">>, 2.0) > encode_float_ascending(<<"hello">>, 1.0)),
  true = (encode_float_descending(<<"hello">>, 1.0) > encode_float_descending(<<"hello">>, 2.0)).




%% == helpers

test_encode_decode([{Encoded, Value} | Rest], Enc, Dec) ->
  Encoded = Enc(<<>>, Value),
  {Value, <<>>} = Dec(Enc(<<>>, Value)),
  test_encode_decode(Rest, Enc, Dec);
test_encode_decode([], _Enc, _Dec) ->
  ok.

edge_case_uint64() ->
  Cases = lists:foldl(fun(I, Acc) ->
                          X = 1 bsl I,
                          [to_uint64(X+1), to_uint64(X), to_uint64(X-1) | Acc]
                      end,
                      [2, 1, 0],
                      lists:seq(2, 64)),
  lists:reverse([ 1 bsl 64 - 1 | Cases ]).

rand_pow_distributed_int63(Count) ->
  Values = lists:foldl(fun(_I, Acc) ->
                           Digits = rand:uniform(63) + 1,
                           X = rand:uniform(1 bsl Digits),
                           Acc2 = case (X bsr (Digits - 1)) of
                                    0 ->
                                      [to_uint64(rand:uniform(1 bsl Digits)) | Acc];
                                    _ -> [X | Acc]
                                  end,
                           Acc2
                       end,
                       [],
                       lists:seq(1, Count)),
  Values.


-endif.