Three Letters In Two Bytes

Introduction

Letters are wasteful. A byte can hold 256 different values, and a message in English uses about thirty of them most of the time: the 26 letters, a space, a full stop, a comma. Thirty-two values need only five bits. Three 5-bit codes fit in sixteen bits, which is one Turbo integer, two bytes. So three letters can travel in the space of two.

Zork does exactly this. Every message in its story file is packed that way, which is how its opening sentence, 83 characters, takes 48 bytes on the disc.

The Codes

Small letters cost one code, capitals two, and anything else, a quote mark or a |, three. Zork's scheme is the same idea, with shift codes and a table of punctuation of its own.

Packing

Pack turns the message into a list of codes, Z, then puts them into integers three at a time:

W[I] := Z[3 * I - 2] shl 10 +
        Z[3 * I - 1] shl 5 +
        Z[3 * I];

shl 10 moves a code up ten bits, shl 5 five. The three codes sit side by side in bits 14 to 10, 9 to 5, and 4 to 0, and the top bit is spare. Zork uses the spare bit to mark the end of a message, and so does Pack:

W[NW] := W[NW] or $8000;

$8000 is the top bit alone, and or sets it. An integer with its top bit set is negative, so the unpacker knows it has the last integer when it finds one below zero.

Unpacking

Unpack takes each integer apart again. shr shifts the other way, and and 31 keeps only the bottom five bits:

C := (W[I] shr (5 * J)) and 31;

for J = 2, 1 and 0. Then a case on the code adds a letter, a space or a full stop, or remembers that the next code is a capital, or the first half of a character by number.

Does It Work, And What Does It Cost

The program packs every message in BEACON.MSG, unpacks it, and checks the result against the original.

Thirty per cent saved, and every message intact. But look at the time: nearly three quarters of a second to unpack one long message, before it is printed, and printing it takes about half a second more. The unpacker builds the message with S := S + ... once for every character, which S6 showed is slow. Packing, unpacking and checking all 27 messages takes about fourteen seconds.

The Code

program Squeeze;
type
  Str255 = string[255];
var
  F: file of Str255;
  Msg, Back: Str255;
  Z: array[1..800] of Byte;
  W: array[1..270] of Integer;
  NZ, NW, K, Chars, Bytes: Integer;
  Same: Boolean;

procedure Add(C: Integer);
begin
  NZ := NZ + 1;
  Z[NZ] := C;
end;

procedure Pack(S: Str255);
var
  I: Integer;
  Ch: Char;
begin
  NZ := 0;
  for I := 1 to Length(S) do
  begin
    Ch := S[I];
    if Ch = ' ' then
      Add(0)
    else if Ch in ['a'..'z'] then
      Add(Ord(Ch) - 96)
    else if Ch in ['A'..'Z'] then
    begin
      Add(27);
      Add(Ord(Ch) - 64);
    end
    else if Ch = '.' then
      Add(28)
    else if Ch = ',' then
      Add(29)
    else
    begin
      Add(30);
      Add(Ord(Ch) shr 5);
      Add(Ord(Ch) and 31);
    end;
  end;
  while NZ mod 3 <> 0 do
    Add(31);
  NW := NZ div 3;
  for I := 1 to NW do
    W[I] := Z[3 * I - 2] shl 10 +
            Z[3 * I - 1] shl 5 +
            Z[3 * I];
  W[NW] := W[NW] or $8000;
end;

function Unpack: Str255;
var
  S: Str255;
  I, J, C, Mode, Hi: Integer;
  Done: Boolean;
begin
  S := '';
  Mode := 0;
  I := 0;
  repeat
    I := I + 1;
    Done := W[I] < 0;
    for J := 2 downto 0 do
    begin
      C := (W[I] shr (5 * J)) and 31;
      case Mode of
        0: case C of
             0: S := S + ' ';
             1..26: S := S + Chr(C + 96);
             27: Mode := 1;
             28: S := S + '.';
             29: S := S + ',';
             30: Mode := 2;
           end;
        1: begin
             S := S + Chr(C + 64);
             Mode := 0;
           end;
        2: begin
             Hi := C;
             Mode := 3;
           end;
        3: begin
             S := S + Chr(Hi shl 5 + C);
             Mode := 0;
           end;
      end;
    end;
  until Done;
  Unpack := S;
end;

begin
  Assign(F, 'BEACON.MSG');
  Reset(F);
  Chars := 0;
  Bytes := 0;
  Same := True;
  for K := 1 to FileSize(F) do
  begin
    Read(F, Msg);
    Pack(Msg);
    Back := Unpack;
    if Back <> Msg then
      Same := False;
    Chars := Chars + Length(Msg);
    Bytes := Bytes + 2 * NW;
  end;
  Writeln('Characters: ', Chars);
  Writeln('Packed bytes: ', Bytes);
  Writeln('All came back: ', Same);
  Seek(F, 20);
  Read(F, Msg);
  Pack(Msg);
  Writeln('Go');
  for K := 1 to 20 do
    Back := Unpack;
  Writeln('Unpacked');
  Writeln(Copy(Back, 1, 38));
  Close(F);
end.

Starting from

A new work file SQUEEZE, on the primer's disc.

What you should see

After about fourteen seconds of packing:

Characters: 2652
Packed bytes: 1854
All came back: TRUE
Go

then about fifteen seconds for twenty unpackings, and

Unpacked
You strike a match and hold it to the

Change One Thing

• Change Add(28) (the full stop) to Add(29). What does the check say, and what would the messages look like?
• Change for K := 1 to 20 (the unpacking loop) to 1 to 1. How long does one unpacking take?
• Change ['a'..'z'] to ['a'..'y']. Does every message still come back? Does the packed size change, and why only a little?

Exercises

14.1 Print each message's length beside its packed size, four pairs to a line.

14.2 Count how many characters needed code 30, the three-code escape.

14.3 Write Show, an unpacker that writes each character to the screen as it decodes it instead of building a string. Time three Shows of the winning message.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

Five bits are enough for small letters, a space and a few signs, and three 5-bit codes fit in one integer: 2,652 characters packed into 1,854 bytes, and every one came back. shl, shr, and and or do the packing. The cost is time: over half a second to unpack a long message in Pascal.

Next

S15, Common Words By Number: Zork's second trick.