Convert a decimal number string to a Base36 number string

Problem/Question/Abstract:

I have a 20 digit string, all numbers, and I would like to convert this to a Base36 to take up less space. I have tried the Borland Radix() routine but this would not work on such a large number. Does anyone have an idea on how to convert the decimal number string to aBase36 number string?

Answer:

Solve 1:

Does the encoding have to result in a string having only "printable" characters (#32..#126) or is any byte value allowed? If so an easy packing method not requiring any complex calculation would be BCD: pack two digits into a byte, giving a 50% size reduction:

function NumStringToBCD(const inStr: string): string;

  function Pack(ch1, ch2: Char): Char;
  begin
    Assert((ch1 >= '0') and (ch1 <= '9'));
    Assert((ch2 >= '0') and (ch2 <= '9'));
    {Ord('0') is $30, so we can just use the low nybble of the character as value.}
    Result := Chr((Ord(ch1) and $F) or ((Ord(ch2) and $F) shl 4))
  end;

var
  i: Integer;
begin
  if Odd(Length(inStr)) then
    Result := NumStringToBCD('0' + inStr)
  else
  begin
    SetLength(Result, Length(inStr) div 2);
    for i := 1 to Length(Result) do
      Result[i] := Pack(inStr[2 * i - 1], inStr[2 * i]);
  end;
end;

function BCDToNumString(const inStr: string): string;

  procedure UnPack(ch: Char; var ch1, ch2: Char);
  begin
    ch1 := Chr((Ord(ch) and $F) + $30);
    ch2 := Chr(((Ord(ch) shr 4) and $F) + $30);
    Assert((ch1 >= '0') and (ch1 <= '9'));
    Assert((ch2 >= '0') and (ch2 <= '9'));
  end;

var
  i: Integer;
begin
  SetLength(Result, Length(inStr) * 2);
  for i := 1 to Length(inStr) do
    UnPack(inStr[i], Result[2 * i - 1], Result[2 * i]);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  S1, S2: string;
begin
  S1 := '15151515151515151515';
  S2 := NumStringToBCD(S1);
  memo1.lines.add('S1: ' + S1);
  memo1.lines.add('Length(S2): ' + IntToStr(Length(S2)));
  memo1.lines.add('S2 unpacked again: ' + BCDToNumString(S2));
end;


Solve 2:

This DecimalStrToBase36Str seems to work on smaller inputs, but I suggest that you check output on the larger inputs.

{ ... }
const
  Base36Digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

type
  tArrayElement = Byte;
  tDoubleElement = Word;
  {tArrayElement  = Word;}
  {tDoubleElement = LongWord;}

const
  SizeOfAryElem = SizeOf(tArrayElement);
  BitsInBufElem = SizeOfAryElem * 8;

function DecimalStrToBase36Str(const Value: string): string;
var
  Man: array[0..19] of tArrayElement;
  NbrManElem, Cry, i, j, n, Tmp: integer;
  Tmp1, Tmp2: packed record
    case byte of
      0: (Wd: tDoubleElement);
      1: (Lo, Hi: tArrayElement);
  end;
begin
  n := length(Value);
  if n <> 20 then
    raise Exception.CreateFmt('Input string must be 20 decimal digits, not %d digits',
      [n]);
  NbrManElem := 0;
  for i := 1 to n do
  begin
    Cry := ord(Value[i]) - ord('0');
    if (Cry < 0) or (Cry > 9) then
      raise Exception.CreateFmt('Input string contains non-decimal digit (%s)',
        [Value[i]]);
    {Multiply accumulation by 10 and add k:}
    for j := 0 to NbrManElem - 1 do
    begin
      Tmp := Man[j] * 10 + Cry;
      Man[j] := Tmp and $FF;
      Cry := Tmp shr 8;
    end;
    if Cry <> 0 then
    begin
      Inc(NbrManElem);
      Man[NbrManElem - 1] := Cry;
    end;
  end;
  SetLength(Result, 14);
  for i := 14 downto 1 do
  begin
    {Divide by 36 and save the remainder:}
    Tmp1.Hi := 0;
    for j := NbrManElem - 1 downto 0 do
    begin
      Tmp1.Lo := Man[j];
      Tmp2.Wd := Tmp1.Wd div 36;
      Assert(Tmp2.Hi = 0);
      Man[j] := Tmp2.Lo;
      Tmp1.Hi := Tmp1.Wd mod 36;
    end;
    Result[i] := Base36Digits[Tmp1.Hi + 1];
    if (NbrManElem > 0) and (Man[NbrManElem - 1] = 0) then
    begin
      dec(NbrManElem);
    end;
  end;
end;