ken@cs.rochester.edu (Ken Yap) (05/01/88)
Is there a portable way to write bitwise left shift and right shift in M2? I have a simple LZ decompressor in Powell's M2 that is compatible with the Unix compress. I'm almost ready to post this to this newsgroup. I'm using the bitoperations extensions at the moment. If there is no portable way to do it, I'll let you fix it yourself, it's only in three places. You also have to provide binary byte i/o. Ken
ken@cs.rochester.edu (Ken Yap) (05/04/88)
Ok, here you go, a LZ decompressor in M2 that handles Unix compress
format. Do what you like with the source. You have to fix the
bitshifting parts, in the last resort you can do multiplies and
divides, there is even a power of two array handy. You also have to
provide binary byte i/o.
I include auxiliary files I used to make it work with Powell's M2
compiler. If you manage to make it work on any other M2 system, I'd be
interested in how much work it took you and how efficient the solution
is. It might tell us something about implementation quality.
Cheers, Ken
#!/bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #!/bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# zcat.mod
# InOut.def
# InOut.c
# Makefile
# This archive created: Tue May 3 17:43:46 1988
# By: Ken Yap ()
export PATH; PATH=/bin:$PATH
echo shar: extracting "'zcat.mod'" '(4370 characters)'
if test -f 'zcat.mod'
then
echo shar: over-writing existing file "'zcat.mod'"
fi
cat << \SHAR_EOF > 'zcat.mod'
MODULE zcat;
(*
** Lempel-Ziv decompressor, compatible with Unix compress.
** For algorithm see original paper or Unix compress source.
** No frills. Reads standard input and writes standard output.
**
** Written to learn M2 bit operations.
** To port this program to other compilers you have to supply
** bit shift operations and binary byte i/o.
** getchar() returns one byte as an unsigned integer or -1 on EOF.
** putchar() writes an unsigned integer as a byte.
** uexit becomes whatever your OS wants to exit with program status.
**
** Ken Yap
** May 1988
** ken@cs.rochester.edu
*)
FROM unix IMPORT
uexit;
FROM InOut IMPORT
WriteString, WriteLn, getchar, putchar;
FROM bitoperations IMPORT
BitShiftLeft, BitShiftRight;
CONST
MAGIC1 = 1FH;
MAGIC2 = 9DH;
BLOCKBIT = 7;
BITMASK = 20H;
BITS = 16;
INITBITS = 9;
HSIZE = 69000;
NHASH = 65535;
SSIZE = 3464;
CLEAR = 256;
FIRST = 257;
TYPE
codeint = INTEGER;
chartype = INTEGER;
buffertype = ARRAY [0..BITS] OF chartype;
VAR
i,
nbits,
maxbits : INTEGER;
powertab : ARRAY [0..BITS] OF INTEGER;
rmask : ARRAY [0..BITS+1] OF BITSET;
blockcompress,
clearflg : BOOLEAN;
maxcode,
maxmaxcode,
freeent : codeint;
codetab : ARRAY [0..HSIZE] OF codeint;
htab : ARRAY [0..NHASH] OF chartype;
destack : ARRAY [0..SSIZE] OF chartype;
offset,
size : INTEGER;
buf : buffertype;
PROCEDURE fread(VAR buffer : buffertype; n : INTEGER) : INTEGER;
VAR
i, c : INTEGER;
BEGIN
FOR i := 0 TO n-1 DO
c := getchar();
IF c = -1 THEN
RETURN (i);
END;
buffer[i] := c;
END;
RETURN (n);
END fread;
PROCEDURE getcode() : codeint;
VAR
code : codeint;
roff, bits, bp : INTEGER;
BEGIN
IF clearflg OR (offset >= size) OR (freeent > maxcode) THEN
IF freeent > maxcode THEN
INC(nbits);
IF nbits = maxbits THEN
maxcode := maxmaxcode
ELSE
maxcode := powertab[nbits] - 1;
END;
END;
IF clearflg THEN
nbits := INITBITS;
maxcode := powertab[nbits] - 1;
clearflg := FALSE;
END;
size := fread(buf, nbits);
IF size <= 0 THEN
RETURN (-1);
END;
offset := 0;
size := (size * 8) - nbits + 1;
END;
bits := nbits;
bp := offset DIV 8;
roff := offset MOD 8;
code := BitShiftRight(buf[bp], roff);
INC(bp);
roff := 8 - roff;
DEC(bits, roff);
IF bits >= 8 THEN
code := code + BitShiftLeft(buf[bp], roff);
INC(bp);
INC(roff, 8);
DEC(bits, 8);
END;
code := code + BitShiftLeft(INTEGER(BITSET(buf[bp]) * rmask[bits]), roff);
INC(offset, nbits);
RETURN (code);
END getcode;
PROCEDURE decompress();
VAR
stackp : INTEGER;
finchar,
code,
oldcode,
incode : codeint;
BEGIN
nbits := INITBITS;
maxcode := powertab[INITBITS] - 1;
FOR code := 0 TO 255 DO
codetab[code] := 0;
htab[code] := code;
END;
IF blockcompress THEN
freeent := FIRST;
ELSE
freeent := 256
END;
oldcode := getcode();
finchar := oldcode;
IF oldcode = -1 THEN
RETURN;
END;
putchar(finchar);
stackp := 0;
code := getcode();
WHILE code > -1 DO
IF (code = CLEAR) AND blockcompress THEN
FOR code := 0 TO 255 DO
codetab[code] := 0;
END;
clearflg := TRUE;
freeent := FIRST - 1;
code := getcode();
IF code = -1 THEN
RETURN
END;
END;
incode := code;
IF code >= freeent THEN
destack[stackp] := finchar;
INC(stackp);
code := oldcode
END;
WHILE code >= 256 DO
destack[stackp] := htab[code];
INC(stackp);
code := codetab[code]
END;
finchar := htab[code];
destack[stackp] := finchar;
INC(stackp);
REPEAT
DEC(stackp);
putchar(destack[stackp]);
UNTIL stackp <= 0;
code := freeent;
IF code < maxmaxcode THEN
codetab[code] := oldcode;
htab[code] := finchar;
freeent := code + 1
END;
oldcode := incode;
code := getcode();
END;
END decompress;
PROCEDURE badformat();
BEGIN
WriteString("Bad COMPRESS file format");
WriteLn();
uexit(1);
END badformat;
BEGIN
rmask[0] := {};
i := 1;
FOR nbits := 0 TO BITS DO
powertab[nbits] := i;
rmask[nbits+1] := rmask[nbits] + BITSET(i);
INC(i, i);
END;
IF (getchar() <> MAGIC1) OR (getchar() <> MAGIC2) THEN
badformat();
END;
maxbits := getchar();
blockcompress := BLOCKBIT IN BITSET(maxbits);
maxbits := maxbits MOD BITMASK;
IF maxbits > BITS THEN
badformat();
END;
maxmaxcode := powertab[maxbits];
size := 0;
offset := 0;
freeent := 0;
clearflg := FALSE;
decompress();
uexit(0);
END zcat.
SHAR_EOF
if test 4370 -ne "`wc -c 'zcat.mod'`"
then
echo shar: error transmitting "'zcat.mod'" '(should have been 4370 characters)'
fi
echo shar: extracting "'InOut.def'" '(316 characters)'
if test -f 'InOut.def'
then
echo shar: over-writing existing file "'InOut.def'"
fi
cat << \SHAR_EOF > 'InOut.def'
DEFINITION MODULE InOut;
EXPORT
Done, Read, Write, WriteLn, WriteString, getchar, putchar;
VAR
Done : BOOLEAN;
PROCEDURE Read(VAR ch : CHAR);
PROCEDURE Write(ch : CHAR);
PROCEDURE WriteLn;
PROCEDURE WriteString(s : ARRAY OF CHAR);
PROCEDURE getchar() : INTEGER;
PROCEDURE putchar(c : INTEGER);
END InOut.
SHAR_EOF
if test 316 -ne "`wc -c 'InOut.def'`"
then
echo shar: error transmitting "'InOut.def'" '(should have been 316 characters)'
fi
echo shar: extracting "'InOut.c'" '(446 characters)'
if test -f 'InOut.c'
then
echo shar: over-writing existing file "'InOut.c'"
fi
cat << \SHAR_EOF > 'InOut.c'
#include <stdio.h>
int InOut_Done = 0;
InOut__init()
{
InOut_Done = 0;
}
InOut_Read(c)
char *c;
{
register char ch;
if ((ch = getchar()) == EOF)
InOut_Done = 1;
else
*c = ch & 0x7f;
}
InOut_Write(c)
char c;
{
putchar(c);
}
InOut_WriteLn()
{
putchar('\n');
}
InOut_WriteString(s, l)
char *s;
int l;
{
while (l-- > 0)
putchar(*s++);
}
int InOut_getchar()
{
return (getchar());
}
InOut_putchar(c)
int c;
{
putchar(c);
}
SHAR_EOF
if test 446 -ne "`wc -c 'InOut.c'`"
then
echo shar: error transmitting "'InOut.c'" '(should have been 446 characters)'
fi
echo shar: extracting "'Makefile'" '(159 characters)'
if test -f 'Makefile'
then
echo shar: over-writing existing file "'Makefile'"
fi
cat << \SHAR_EOF > 'Makefile'
MODFLAGS = -g
zcat: zcat.o InOut.o
mod $(MODFLAGS) -o zcat zcat.o InOut.o
zcat.o: zcat.mod
mod $(MODFLAGS) -c zcat.mod
InOut.o: InOut.c
cc -O -c InOut.c
SHAR_EOF
if test 159 -ne "`wc -c 'Makefile'`"
then
echo shar: error transmitting "'Makefile'" '(should have been 159 characters)'
fi
# End of shell archive
exit 0