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: ScanLinePtr ← 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: DWScanLinePtr ← 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: DWScanLinePtr ← 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: ScanLinePtr;
==========
FlushBlankLines:
PROCEDURE =
INLINE
BEGIN
IF blankLn # 0
THEN {
FOR i:
CARDINAL
IN [0..blankLn)
DO
PutByte[enc]; encLines ← encLines + 1; ENDLOOP;
blankLn ← 0;
};
END; -- FlushBlankLines
==========
GetEstimateAndLimits:
PROCEDURE RETURNS [c:
INTEGER, nw1st: BitWrdIndex, nwLast: BitWrdIndex, iRun:
CARDINAL] =
BEGIN
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
END; --GetEstimateAndLimits
==========
GetHTNPredictData:
PROCEDURE
RETURNS [nibCt:
INTEGER] =
BEGIN
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: ScanLinePtr ← 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
END; -- GetHTNPredictData
==========
GetLINPredictData:
PROCEDURE [nwLine: DWScanLinePtr, pvLine: DWScanLinePtr]
RETURNS [c:
INTEGER] =
BEGIN
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
md1: MACHINE DEPENDENT RECORD [a, b: CARDINAL];
md2: MACHINE DEPENDENT RECORD [a, b: CARDINAL];
md3: MACHINE DEPENDENT RECORD [a, b: CARDINAL];
md1 ← LOOPHOLE[nwLine[i]]; md2 ← LOOPHOLE[pvLine[i]];
md3.a ← Basics.BITXOR[md1.a, md2.a]; md3.b ← Basics.BITXOR[md1.b, md2.b];
kWord ← linBuf[i] ← Basics.DBITXOR[nwLine[i], pvLine[i]];
kWord ← linBuf[i] ← LOOPHOLE[md3];
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;
END; --GetLINPredictData
============
GoENC:
PROCEDURE [iRun:
CARDINAL] =
iRun passed as argument for efficiency reason
BEGIN
kmpVal: CARDINAL;
kWd: CARDINAL;
nibble: CARDINAL;
nibInd: INTEGER;
nibTrn: INTEGER;
shftr: CARDINAL;
======
Go11ggggggabcd:
PROCEDURE =
INLINE
BEGIN
Put3Nibbles[6000B + Basics.BITAND[Basics.BITSHIFT[iRun, 4], 1760B] + nibble];
iRun ← 0;
END; --Go11ggggggabcd
======
Go10XXorA:
PROCEDURE =
INLINE BEGIN
IF iRun = 0
THEN
Output if the form 10XXorA
PutNibble[8 + nibTrn]
ELSE {
PutByte[Basics.BITAND[Basics.BITSHIFT[iRun, 2], 174B] + nibTrn];
iRun ← 0;
};
END; -- 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 BEGIN
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;
END; -- IF nibble = 0 ELSE
ENDLOOP; -- every nibble
adjust for trailing zero nibbles of word
iRun ← iRun + (nNibs - nibInd);
ENDLOOP; -- every word
END; -- GoENC
============
GoENCorRAW:
PROCEDURE =
BEGIN
This routine will decide whether RAW mode or ENC mode is more feasible.
IF nwNibCt >= iRAWCt
THEN GoRAW[]
ELSE BEGIN
Scan line to be encoded with no prediction
linCount ← 0;
encLines ← encLines + 1;
PutByte[enc];
currLine ← LOOPHOLE[nwLine];
iFirst ← nw1st;
iLast ← nwLast;
GoENC[iRun];
END;
END; -- GoENCorRAW
===========
GoLINorRAW:
PROCEDURE =
BEGIN
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
};
END; -- GoLINorRAW
============
GoLINorHTNorRAW:
PROCEDURE =
BEGIN
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
};
};
END; --GoLINorHTNorRAW
============
GoRAW:
PROCEDURE =
BEGIN
Go RAW!
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;
END; -- 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 BEGIN
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 BEGIN
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
};
END;
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[];
END;
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;
END; -- CompressPlate