Base86, формат представления данных

Февраль 1, 2015 — Шарахов А.П.

В статье предлагается новый удобный формат, использующий для текстового представления данных меньше памяти, чем Base64. Табличные алгоритмы кодирования и декодирования обеспечивают ему более высокую скорость по сравнению с Base85. Кроме того, английский текст после кодирования сохраняет некоторую читаемость, и это еще не все...

Base64 имеет такое большое число вариантов, что порой бывает трудно выбрать нужный. Алфавит Base85 содержит мои любимые кавычки, а скорость работы падает на little-endian машине. Пора положить этому конец.

Немного формализма

Давайте вспомним, что 3^4=81, 256/86<3. Эти два замечательных соотношения позволяют кодировать группу из 4 байтов в группу из 5 ASCII-символов 86-символьного алфавита.

В самом деле, разделим значение каждого байта на 86 и сформируем из четырех полученных частных код первого символа в диапазоне 0..80. Остальные 4 кода в диапазоне 0..85 - это остатки от операций деления. Значения символов, соответствующих вычисленным кодам возьмем из таблицы. Обратное преобразование очевидно.

Длинные цепочки байтов как обычно кодируем группами по 4 байта. Последнюю группу байтов, длина которой может оказаться меньше, дополняем необходимым количеством нулей, а после кодирования столько же символов отбрасываем. При декодировании поступаем аналогично.

Достоинства

Кроме очевидной экономичности представления данных, прежде всего, скорость. Алгоритм может быть построен без относительно тяжелых операций деления. Учет сетевого порядка байтов производится при вычислениях с кодом первого символа без дополнительных операций.

Некоторая читаемость английского текста после кодирования достигается выбором необходимого порядка следования символов в алфавите. При известном желании и упорстве в этом

}Hell{ovwocrld

без труда можно разглядеть

Hello world

8 наиболее проблемных символов "&'/<>\` исключены из алфавита.

В алфавите имеется 5 свободных символов QRSTU, которые никогда не окажутся на первом месте в пятерке. Эти коды в случае крайней необходимости теоретически можно будет использовать для специальных целей. Например, для кодирования наиболее часто повторяющихся последовательностей. Автор, однако, считает, что архиватор лучше, и выступает против этой идеи)

Ничего не забыл?

Ах, да, исходники референсного дизайна:

{$WARN UNSAFE_TYPE OFF}
{$WARN UNSAFE_CODE OFF}
{$WARN UNSAFE_CAST OFF}
unit ShaBase86;
 
// ShaBase86 and encode/decode functions
// (c) Aleksandr Sharahov 2002
// Current version 2015-01-31
// Free for any use
 
interface
 
procedure ShaBase86EncodePacket(Input, Output: pAnsiChar);                  //4 => 5
procedure ShaBase86EncodePackets(Input, Output: pAnsiChar; Count: integer); //4 => 5
procedure ShaBase86DecodePacket(Input, Output: pAnsiChar);                  //5 => 4
procedure ShaBase86DecodePackets(Input, Output: pAnsiChar; Count: integer); //5 => 4
procedure ShaBase86ReinitTables;
 
var
  //Alphabet consists of 86 of 94 printable ASCII characters:
  //                 10 digits: 0123456789
  //          26 small letters: abcdefghijklmnopqrstuvwxyz
  //            26 big letters: ABCDEFGHIJKLMNOPQRSTUVWXYZ
  // and 24 special characters: !#$%()*+,-.:;=?@[]^_{|}~
  //      8 characters omitted: "&'/<>\`
  //ShaBase86-encoded text is readable because characters are placed in alphabet according their ASCII codes.
  ShaBase86Alphabet: array[0..85] of AnsiChar= 'VWXYZ[~]^_!abcde'
                                             + 'fghijklmnopqrstu'
                                             + 'vwxyz{|}()*+,-.%'
                                             + '0123456789:;#=$?'
                                             + '@ABCDEFGHIJKLMNO'
                                             + 'PQRSTU';
 
//This is LE-implementation.
//BE-implementation calculates the same packet value including the first character.
implementation
 
var
  ShaBase86EncodeTable: array[0..255] of integer;
  ShaBase86DecodeTable0: array[0..255] of integer;
  ShaBase86DecodeTable1: array[0..255] of integer;
 
procedure ShaBase86EncodePacket(Input, Output: pAnsiChar);
var
  c, d, e, f: integer;
begin;
  c:=pInteger(Input)^;
  e:=ShaBase86EncodeTable[c shr 24]; f:=e and integer($FF000000);
  d:=ShaBase86EncodeTable[c shr 16 and $FF]; e:=e * 3; e:=e + d; f:=f + d and $FF0000;
  d:=ShaBase86EncodeTable[c shr  8 and $FF]; e:=e * 3; e:=e + d; f:=f + d and $FF00;
  d:=ShaBase86EncodeTable[c        and $FF]; e:=e * 3; e:=e + d; f:=f + d shr 24;
  Output[0]:=ShaBase86Alphabet[e and 255];
  pInteger(Output+1)^:=f;
  end;
 
procedure ShaBase86EncodePackets(Input, Output: pAnsiChar; Count: integer);
var
  c, d, e, f, OutputOffset: integer;
  Terminator: pAnsiChar;
begin;
  //to optimize speed of Delphi code we don't use while-loop with dec(Count)
  if Count>0 then begin;
    Terminator:=@Input[4*Count];
    OutputOffset:=Output-Input;
    repeat;
      c:=pInteger(Input)^;
      e:=ShaBase86EncodeTable[c shr 24]; f:=e and integer($FF000000);
      d:=ShaBase86EncodeTable[c shr 16 and $FF]; e:=e * 3; e:=e + d; f:=f + d and $FF0000;
      d:=ShaBase86EncodeTable[c shr  8 and $FF]; e:=e * 3; e:=e + d; f:=f + d and $FF00;
      d:=ShaBase86EncodeTable[c        and $FF]; e:=e * 3; e:=e + d; f:=f + d shr 24;
      Input[OutputOffset]:=ShaBase86Alphabet[e and 255];
      pInteger(Input+OutputOffset+1)^:=f;
      inc(Input, 4);
      inc(OutputOffset);
      until Input>=Terminator;
    end;
  end;
 
procedure ShaBase86DecodePacket(Input, Output: pAnsiChar);
var
  e, f: integer;
begin;
  e:=ShaBase86DecodeTable0[ord(Input[0])];
  f:=pInteger(Input+1)^;
  e:=e + ShaBase86DecodeTable1[f shr 24        ] and integer($FF000000);
  e:=e + ShaBase86DecodeTable1[f        and 255] and $FF;
  e:=e + ShaBase86DecodeTable1[f shr  8 and 255] and $FF00;
  f:=    ShaBase86DecodeTable1[f shr 16 and 255] and $FF0000;
  pInteger(Output)^:=e + f;
  end;
 
procedure ShaBase86DecodePackets(Input, Output: pAnsiChar; Count: integer);
var
  e, f: integer;
begin;
  while Count>0 do begin;
    dec(Count);
    e:=ShaBase86DecodeTable0[ord(Input[0])];
    f:=pInteger(Input+1)^;
    e:=e + ShaBase86DecodeTable1[f shr 24        ] and integer($FF000000);
    e:=e + ShaBase86DecodeTable1[f        and 255] and $FF;
    e:=e + ShaBase86DecodeTable1[f shr  8 and 255] and $FF00;
    f:=    ShaBase86DecodeTable1[f shr 16 and 255] and $FF0000;
    pInteger(Output)^:=e + f;
    inc(Input, 5);
    inc(Output, 4);
    end;
  end;
 
procedure ShaBase86ReinitTables;
var
  i, j, m, n: integer;
begin;
  for i:=0 to 255 do begin;
    j:=ord(ShaBase86Alphabet[i mod 86]);
    ShaBase86EncodeTable[i]:=j * $01010100 or i div 86;
    ShaBase86DecodeTable0[i]:=0;
    ShaBase86DecodeTable1[i]:=0;
    end;
  for i:=0 to 85 do ShaBase86DecodeTable1[ord(ShaBase86Alphabet[i])]:=i * $01010101;
  for i:=0 to 80 do begin;
    n:=0; m:=86; j:=i;
    while j>0 do begin;
      n:=n + j mod 3 * m;
      m:=m shl 8;
      j:=j div 3;
      end;
    ShaBase86DecodeTable0[ord(ShaBase86Alphabet[i])]:=n;
    end;
  end;
 
initialization
 
  ShaBase86ReinitTables;
 
end.

на главную