## 2003. december 22., hétfő

### 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;