Quote:

> >BTW, there is an elegant trick (due to Mssnbck I think) to

> >read/write 4-byte integers in variable number of bytes.

> >I saw it in one of Stefan Ludwig's program and used it

> >ever since.

> Would you elaborate on this, or at least point us to the

> relevent module?

> Thanks,

> Michael

Numbers can be encoded in a machine independent format (least significant byte first,

base 128, most significant bit as "stop bit", this bit cleared meaning stop).

I will try to explain that for positive and negative numbers separately:

For positive numbers, the loop is simply:

writing the 7 least significant bits (plus adding 128, which makes it a number

in the range 128..255, i.e. the most significant bit is set)

shifting the number 7 bits to the right

After the loop, the number is <= 63, i.e. it can be represented with 6 bits, therefore the

most significant bit is not set.

For negative numbers we have to understand what x MOD 128 and x DIV 128 do:

I will motivate it with smaller numbers (x MOD 4 and x DIV 4):

x MOD y and x DIV y are defined in the language report as x = (x DIV y) * y + (x MOD y),

the result of the module operation is always positive.

x x (binary) x (bin, last 2 bits) x MOD 4 x DIV 4

-1 1111 1111 11 3 -1

-2 1111 1110 10 2 -1

-3 1111 1101 01 1 -1

-4 1111 1100 00 0 -1

-5 1111 1011 11 3 -1

-6 1111 1010 10 2 -1

We see that x MOD 128 returns the 7 least significant bits and that x DIV 128 shifts

x 7 bits to the right.

Therefore, for negative numbers, the loop is simply:

writing the 7 least siginificant bits (plus adding 128, as above)

shifting the number 7 bits to the right

After the loop, the number is >= -64, x MOD 128 is in the range of 64..127 (see below),

i.e. the most significant bit is not set.

x x (binary) x MOD 128

-64 1111 1100 0000 100 0000 = 64

-63 1111 1100 0001 100 0001 = 65

-1 1111 1111 1111 111 1111 = 127

PROCEDURE WriteNum* (VAR R: Rider; x: LONGINT);

BEGIN

WHILE (x < - 64) OR (x > 63) DO Write(R, CHR(x MOD 128 + 128)); x := x DIV 128 END ;

Write(R, CHR(x MOD 128))

END WriteNum;

The reverse operations are performed on reading the number:

For positive numbers:

The loop converts all the 7 bit chunks (which have the most significant bit set) by

adding the number (decremented by 128 and shifted the appropriate number of bits to

the left)

After the loop the number is <= 63 (see WriteNum), therefore ch MOD 64 is ch, x DIV 64 = 0,

which means that the number is simply shifted the appropriate number of bits and is added

For negative numbers:

The loop converts all the 7 bit chunks (which have the most significant bit set) by

adding the number (decremented by 128 and shifted the appropriate number of bits to

the left).

After the loop the number is in the range of 64..127 (see above), ch MOD 64 is 0..63,

(ch DIV 64) * 64 is 64, therefore ORD(ch) MOD 64 - ORD(ch) DIV 64 * 64 is in the range of

-64..-1. Shifting a negative number the appropriate number of bits to the left and adding it to

the previous sum yields the same negative number that we had before writing it with

WriteNum.

PROCEDURE ReadNum* (VAR R: Rider; VAR x: LONGINT);

VAR s: SHORTINT; ch: CHAR; n: LONGINT;

BEGIN s := 0; n := 0; Read(R, ch);

WHILE ORD(ch) >= 128 DO INC(n, ASH(ORD(ch) - 128, s) ); INC(s, 7); Read(R, ch) END ;

x := n + ASH(ORD(ch) MOD 64 - ORD(ch) DIV 64 * 64, s)

END ReadNum;

Note: The operations are very efficient for small numbers (-64..63) regarding the number

of operations needed to read and write and also the number of bytes needed for

binary representation.

The largest possible numbers (2147483647 for 4 byte integers) need only one byte overhead,

most numbers are stored in a compact way thus saving space.

Example:

1567

WriteNum:

(1567 MOD 128) + 128 = 159, (1567 DIV 128) = 12

Representation on file: 159 12

ReadNum:

159 - 128 = 31, ASH(12, 7) = 1536, 1536 + 31 = 1567

-1567

WriteNum:

(-1567 MOD 128) + 128 = 225, -1567 DIV 128 = -13, -13 MOD 128 = 115

Representation on file: 225 115

ReadNum

225 - 128 = 97, 115 MOD 64 = 51, 115 DIV 64 * 64 = 64, 51 - 64 = -13, ASH(-13, 7) = -1664

-1664 + 97 = -1567

2147483647

WriteNum

2147483647 MOD 128 + 128 = 255, 2147483647 DIV 128 = 16777215

16777215 MOD 128 + 128 = 255, 16777215 DIV 128 = 131071

131071 MOD 128 + 128 = 255, 131071 DIV 128 = 1023

1023 MOD 128 + 128 = 255, 1023 DIV 128 = 7

Representation on file: 255 255 255 255 7

The explanation has become a bit lenghty, but I think the ideas behind it are

nice enough!

Chris

--

DDipl.-Ing. Christoph Steindl University of Linz

Phone: +43-732-2468-7134 Practical Computer Science

Fax: +43-732-2468-7138 Freistaedterstrasse 315

http://www.ssw.uni-linz.ac.at/Staff/CS.html