CompressPlate:
PUBLIC
PROCEDURE [scanLen:
CARDINAL,
scanLineProc: ScanLineProc, putBitsProc: PutBitsProc]
RETURNS [xPixels:
CARDINAL, byteSize:
LONG
CARDINAL] = {
nNibs: CARDINAL = 4; -- Number of nibbles in a word
nRange: CARDINAL = 8; -- HTN predictor sample (bits)
IMG code
enc: CARDINAL = 2; -- ENC mode
eoi: CARDINAL = 113; -- End of image
htn: CARDINAL = 3; -- HTN mode
lin: CARDINAL = 1; -- LIN mode
raw: CARDINAL = 0; -- Raw (ie., no encoding)
soi: CARDINAL = 112; -- Start of image
maxLINCount: CARDINAL = 15; -- Maximum consequtive LIN mode lines
nibMask: ARRAY [0..nNibs) OF CARDINAL = [170000B, 7400B, 360B, 17B];
Mask array to get nibbles from a word
nibVal:
ARRAY [0..15]
OF
INTEGER = [
0, 3, 2, -4, 1, -5, -6, -7, 0, -9, -10, -11, -12, -13, -14, -15];
This table of values enable the appropriate bit representation and descriptor employment for encoding a given nibble of prediction output.
IF nibVal[nibble] < 0 THEN prediction output has more than one bit on.
IF nibVal[nibble] >= 0 THEN prediction output has only one bit on.
Note: nibVal[0] is not used.
Local variables used during CompressPlate
Parameters used in estimating feasibility of various modes
iRAWPercent: INTEGER ¬ 67;
iRAWCt:
INTEGER ¬ 0;
A limit representing the point at which to output a raster line in its raw form rather than in one of the encoded forms.
minNibPercent: INTEGER ¬ 1;
minNibCt:
INTEGER ¬ 0;
A limit repesenting the point at which an encoded prediction result indicates that a desirable level of compression is achievable. The value of minNibCt represents the percentage for comparison with the given predicted results.
debugLine: CARDINAL ¬ LAST[CARDINAL];
cBits: LONG CARDINAL ¬ 0; -- Total bits in compressed image
blankLn: CARDINAL ¬ 0; -- Current # of contiguous blank lines
currLine: ScanLineRef ¬ NIL; -- Current scan line used by GoENC.
It should be equal to nwLine,
pvLine or address of htnBuf.
encLines: CARDINAL ¬ 0; -- Number lines in ENC mode
htnLines: CARDINAL ¬ 0; -- Number of lines in HTN mode
htnNibCt: INTEGER ¬ 0; -- Number of non-zero nibble resulting
from HTN predicition mode
iFirst: CARDINAL ¬ 0; -- Index of first dword in currLine used by
GoEnc when encoding.
iRun: CARDINAL ¬ 0; -- Running count of zero words
iLast: CARDINAL ¬ 0; -- Index of last dword in currLine used by
GoEnc when encoding.
linCount: CARDINAL ¬ 0; -- Consecutive # of LIN mode lines
linLines: CARDINAL ¬ 0; -- Number of lines in LIN mode
linNibCt: INTEGER ¬ 0; -- Number of non-zero nibble
resulting from LIN prediction mode.
lastWord: BitWrdIndex ¬ 0; -- Last word in a line
nwLine: DWScanLineRef ¬ NIL; -- Pointer to current scan line
nwNibCt: INTEGER ¬ 0; -- non-zero nibble count in current line
nw1st: BitWrdIndex ¬ 0; -- Index to 1st non-zero dword in
current line
nwLast: BitWrdIndex ¬ 0; -- Index to last non-zero dword in
current line
pvLine: DWScanLineRef ¬ NIL; -- Pointer to last scan line. If
LIN mode is utilized, the XORed
bits of the line will be put here.
pvNibCt: INTEGER; -- non-zero nibble count in previous line
pv1st: BitWrdIndex ¬ 0; -- Pointer to 1st non-zero dword in
previous line
pvLast: BitWrdIndex ¬ 0; -- Pointer to last non-zero dword in
previous line
rawLines: CARDINAL ¬ 0; -- Number of lines in RAW mode
scnLines: CARDINAL ¬ 0; -- Total number of scan lines
totalBits: LONG CARDINAL ¬ 0; -- Total number of bits in image
PutBits: PutBitsProc ¬ NIL;
dummyLine1: ScanLineRef;
FlushBlankLines:
PROCEDURE =
INLINE {
IF blankLn # 0
THEN {
FOR i:
CARDINAL
IN [0..blankLn)
DO
PutByte[enc]; encLines ¬ encLines + 1; ENDLOOP;
blankLn ¬ 0;
};
}; -- FlushBlankLines
GetEstimateAndLimits:
PROCEDURE RETURNS [c:
INTEGER, nw1st: BitWrdIndex, nwLast: BitWrdIndex, iRun:
CARDINAL] = {
This routine will compute various limits that are used
later in determining which prediction model to use.
lWord, hWord: CARDINAL;
nw1st ¬ 0;
c ¬ 0;
FOR i:
CARDINAL
IN [0..lastWord]
DO
-- For every dword
IF nwLine[i] # 0
THEN {
-- found non zero word.
nw1st ¬ i;
FOR ind:
CARDINAL
IN [i..lastWord]
DO
-- every dword
IF nwLine[ind] # 0
THEN {
nwLast ¬ ind;
IF (lWord ¬ Basics.LowHalf[nwLine[ind]]) # 0
THEN {
IF Basics.BITAND[lWord, 17B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 360B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 7400B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 170000B] # 0 THEN c ¬ c + 1;
};
IF (hWord ¬ Basics.HighHalf[nwLine[ind]]) # 0
THEN {
IF Basics.BITAND[hWord, 17B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 360B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 7400B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 170000B] # 0 THEN c ¬ c + 1;
};
}; -- nwLine[ind] # 0
ENDLOOP;
EXIT;
}; -- nwLine[i] # 0
ENDLOOP;
iRun ¬ nw1st; -- running count of zero words
}; --GetEstimateAndLimits
GetHTNPredictData:
PROCEDURE
RETURNS [nibCt:
INTEGER] = {
This routine will compute htnNibCt which are used later
in determining whethter HTN mode is feasible for the line.
first: CARDINAL ¬ nw1st * 2;
last: CARDINAL;
lastDWord: CARDINAL ¬ lastWord;
kWord: CARDINAL;
pvByte: CARDINAL ¬ 0;
nLine: ScanLineRef ¬ LOOPHOLE[nwLine];
nibCt ¬ 0;
Get that last word. Had to add 2 since we are usually
dealing with double words.
last ¬ MIN[((nwLast * 2) + 2) + 1, (lastWord * 2) + 1];
FOR i:
CARDINAL
IN [first..last]
DO
--every word
kWord ¬ Basics.
BITXOR[
Basics.BITSHIFT[pvByte, 8] + Basics.HighByte[nLine[i]], nLine[i]];
Count the number of non-zero nibbles
IF kWord # 0
THEN {
IF Basics.BITAND[kWord, 17B] # 0 THEN nibCt ¬ nibCt + 1;
IF Basics.BITAND[kWord, 360B] # 0 THEN nibCt ¬ nibCt + 1;
IF Basics.BITAND[kWord, 7400B] # 0 THEN nibCt ¬ nibCt + 1;
IF Basics.BITAND[kWord, 170000B] # 0 THEN nibCt ¬ nibCt + 1;
};
htnBuf[i] ¬ kWord;
pvByte ¬ Basics.LowByte[nLine[i]];
ENDLOOP; -- every byte
}; -- GetHTNPredictData
GetLINPredictData:
PROCEDURE [nwLine: DWScanLineRef, pvLine: DWScanLineRef]
RETURNS [c:
INTEGER] = {
This routine will compute linNibCt (count of non-zero
nibble used in LIN mode. iFirst and iLast which are used
when encoding the line difference are also obtained.
obtain the limits where the XOR can start
kWord: LONG CARDINAL;
lWord, hWord: CARDINAL;
iFirst ¬ MIN[nw1st, pv1st];
iLast ¬ MAX[nwLast, pvLast];
set the pointer of line used by encoding routines to
pvLine (LIN XOR results are stored in linBuf)
c ¬ -1;
FOR i:
CARDINAL
IN [iFirst..iLast]
DO
-- every non-zero dword
XOR line
kWord ¬ linBuf[i] ¬ Basics.DoubleXor[nwLine[i], pvLine[i]];
IF kWord # 0
THEN {
IF (lWord ¬ Basics.LowHalf[kWord]) # 0
THEN {
IF Basics.BITAND[lWord, 17B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 360B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 7400B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[lWord, 170000B] # 0 THEN c ¬ c + 1;
};
IF (hWord ¬ Basics.HighHalf[kWord]) # 0
THEN {
IF Basics.BITAND[hWord, 17B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 360B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 7400B] # 0 THEN c ¬ c + 1;
IF Basics.BITAND[hWord, 170000B] # 0 THEN c ¬ c + 1;
};
};
ENDLOOP; -- every non-zero dword
c ¬ c + 1;
}; --GetLINPredictData
GoENC:
PROCEDURE [iRun:
CARDINAL] = {
iRun passed as argument for efficiency reason
kmpVal: CARDINAL;
kWd: CARDINAL;
nibble: CARDINAL;
nibInd: INTEGER;
nibTrn: INTEGER;
shftr: CARDINAL;
Go11ggggggabcd:
PROCEDURE =
INLINE {
Put3Nibbles[6000B + Basics.BITAND[Basics.BITSHIFT[iRun, 4], 1760B] + nibble];
iRun ¬ 0;
}; --Go11ggggggabcd
Go10XXorA:
PROCEDURE =
INLINE {
IF iRun = 0
THEN
Output if the form 10XXorA
PutNibble[8 + nibTrn]
ELSE {
PutByte[Basics.BITAND[Basics.BITSHIFT[iRun, 2], 174B] + nibTrn];
iRun ¬ 0;
};
}; -- Go10XXorA
Main of GoENC
change running count of non-zero words to non-zero nibbles
iRun ¬ iRun * nNibs * 2;
change iFirst and iLast to words indices
iFirst ¬ iFirst * 2;
iLast ¬ (iLast * 2) + 1;
FOR i:
CARDINAL
IN [iFirst..iLast]
DO
-- every word
kWd ¬ currLine[i];
nibInd ¬ 0;
WHILE kWd # 0
DO
-- every nibble
nibble ¬ Basics.BITAND[kWd, nibMask[nibInd]];
nibInd ¬ nibInd + 1;
IF nibble = 0 THEN iRun ¬ iRun + 1
ELSE
{
kWd ¬ kWd - nibble;
nibble ¬ Basics.BITSHIFT[nibble, -(Basics.bitsPerWord - 4 * nibInd)];
nonZero Nibble obtained. Encode run length
shftr ¬ Basics.BITSHIFT[iRun, -2];
kmpVal ¬ Basics.BITAND[shftr, 1760B];
IF kmpVal # 0
THEN {
11gggggg0000 case
Put3Nibbles[kmpVal + 6000B]; -- get rid of most iRun
iRun ¬ Basics.BITAND[iRun, 77B]};
Determine Descriptor to be used for data nibble
IF iRun > 25
THEN {
Go11ggggggabcd[];
LOOP; -- done with this nibble
};
Descriptor determination requires nibble be evaluated
nibTrn ¬ nibVal[nibble];
IF nibTrn >= 0
THEN {
Go10XXorA[];
LOOP; -- done with this nibble
};
Nibble has more than one bit on
IF iRun > 1
THEN {
Go11ggggggabcd[];
LOOP; -- done with this nibble
};
Encode using Type 'B short descriptor
PutByte[140B - (nibTrn + nibTrn) + iRun];
iRun ¬ 0;
}; -- IF nibble = 0 ELSE
ENDLOOP; -- every nibble
adjust for trailing zero nibbles of word
iRun ¬ iRun + (nNibs - nibInd);
ENDLOOP; -- every word
}; -- GoENC
GoENCorRAW:
PROCEDURE = {
This routine will decide whether RAW mode or ENC mode is more feasible.
IF nwNibCt >= iRAWCt THEN GoRAW[]
ELSE {
Scan line to be encoded with no prediction
linCount ¬ 0;
encLines ¬ encLines + 1;
PutByte[enc];
currLine ¬ LOOPHOLE[nwLine];
iFirst ¬ nw1st;
iLast ¬ nwLast;
GoENC[iRun];
};
}; -- GoENCorRAW
GoLINorRAW:
PROCEDURE = {
This routine will decide whether LIN mode or RAW mode is more feasible.
IF linNibCt >= iRAWCt THEN GoRAW[]
ELSE {
Use LIN mode. Remember that pvLine was used as buffer
for XORed bits
linCount ¬ linCount + 1;
linLines ¬ linLines + 1;
currLine ¬ LOOPHOLE[linBuf];
PutByte[lin];
iRun ¬ iFirst; -- adjust running count of zero words
GoENC[iRun]; -- encode
};
}; -- GoLINorRAW
GoLINorHTNorRAW:
PROCEDURE = {
This routine is faced with a decision whether to go with LIN, HTN or RAW mode
IF (linNibCt < htnNibCt) AND (linNibCt > 0) THEN GoLINorRAW[]
ELSE {
IF htnNibCt > iRAWCt THEN GoRAW[]
ELSE {
HTN mode seems most feasible
linCount ¬ 0;
htnLines ¬ htnLines + 1;
PutByte[htn];
iFirst ¬ nw1st;
iLast ¬ MIN[nwLast + 1, lastWord];
currLine ¬ htnBuf;
iRun should remain the same.
GoENC[iRun]; -- encode
};
};
}; --GoLINorHTNorRAW
GoRAW:
PROCEDURE = {
linCount ¬ 0;
rawLines ¬ rawLines + 1;
PutByte[0];
FOR i:
CARDINAL
IN [0..lastWord]
DO
PutWord[Basics.LowHalf[nwLine[i]]];
PutWord[Basics.HighHalf[nwLine[i]]];
ENDLOOP;
}; -- GoRAW;
Put3Nibbles:
PROCEDURE [val:
CARDINAL] =
INLINE {
PutBits[val, 12]; cBits ¬ cBits + 12};
PutByte:
PROCEDURE [val:
CARDINAL] =
INLINE {
PutBits[val, Basics.bitsPerByte]; cBits ¬ cBits + Basics.bitsPerByte};
PutNibble:
PROCEDURE [val:
CARDINAL] =
INLINE {
PutBits[val, 4]; cBits ¬ cBits + 4};
PutWord:
PROCEDURE [val:
CARDINAL] =
INLINE {
PutBits[val, Basics.bitsPerWord]; cBits ¬ cBits + Basics.bitsPerWord};
Main of CompressPlate
Change prediction estimate parameter from % to nibbles
iRAWCt ¬ Basics.LowHalf[Basics.LongMult[iRAWPercent, scanLen] / 400];
minNibCt ¬ Basics.LowHalf[Basics.LongMult[minNibPercent, scanLen] / 400];
PutBits ¬ putBitsProc;
lastWord ¬ ((scanLen + 31) / 32) - 1;
PutWord[0]; -- Reserved
PutWord[nRange];
PutWord[scanLen]; -- scan length
PutByte[soi]; -- Put start of image
blankLn ¬ 0;
iRun ¬ 0;
nw1st ¬ 0;
nwLast ¬ 0;
nwNibCt ¬ 0;
linCount ¬ 0;
DO
-- every scan line
scnLines ¬ scnLines + 1;
totalBits ¬ totalBits + scanLen;
[dummyLine1, dummyLine2] ¬ scanLineProc[];
nwLine ¬ LOOPHOLE[dummyLine1];
pvLine ¬ LOOPHOLE[dummyLine2];
IF nwLine = NIL THEN EXIT; -- no more
Set up predictor parameters from previous line
pvNibCt ¬ nwNibCt;
pv1st ¬ nw1st;
pvLast ¬ nwLast;
IF scnLines = debugLine THEN Runtime.CallDebugger["Desired line encountered"L];
Compute estimate and limits for encoding this line
[nwNibCt, nw1st, nwLast, iRun] ¬ GetEstimateAndLimits[];
IF nwNibCt = 0 THEN blankLn ¬ blankLn + 1
ELSE {
Output deferred blank lines, if any
FlushBlankLines[];
See if short-cut estimate for encoding data can be used
IF nwNibCt < minNibCt
THEN {
GoENCorRAW[]; -- output current line in ENC or RAW mode
LOOP;
}; -- done with this line
See if LIN mode is feasible
linNibCt ¬ -1;
IF ((2 *
ABS[nwNibCt - pvNibCt]) < nwNibCt)
AND (linCount < maxLINCount)
THEN {
get linNibCt for LIN mode
linNibCt ¬ GetLINPredictData[nwLine, pvLine];
Try short-cut estimate for LIN mode
IF linNibCt < minNibCt
THEN {
GoLINorRAW[];
LOOP; -- done with this line
};
};
Short-cut method for LIN failed, see if HTN can be used
htnNibCt ¬ GetHTNPredictData[]; -- htnNibCt obtained
Results from feasible prediction modes have been obtained. Use results to estimate most compressable mode to employ
IF nwNibCt > htnNibCt
THEN {
GoLINorHTNorRAW[]; -- Try LIN, HTN, or RAW
LOOP; -- done with this line
};
IF linNibCt < 0
OR linNibCt >= nwNibCt
THEN {
GoENCorRAW[]; -- all prediction not feasible, ENC or RAW
LOOP; -- done with this line
};
Try Raw or LIN mode
GoLINorRAW[];
};
ENDLOOP; -- every scan line
Ensure at least one line is output
IF rawLines + encLines + linLines + htnLines = 0
THEN {
PutByte[enc];
encLines ¬ encLines + 1;
};
PutByte[eoi]; -- End of image
xPixels ¬ encLines + linLines + htnLines + rawLines;
byteSize ¬ (cBits + Basics.bitsPerByte - 1) / Basics.bitsPerByte;
}; -- CompressPlate