<> <> <> <> DIRECTORY Basics USING [bitsPerByte, bitsPerWord, BITAND, BITSHIFT, BITXOR, HighByte, HighHalf, LongMult, LowByte, LowHalf], XeroxCompress; XeroxCompressImpl: PROGRAM IMPORTS Basics EXPORTS XeroxCompress = BEGIN OPEN XeroxCompress; <> <<================>> <> <<================>> htnBuf: ScanLinePtr _ NIL; -- Buffer to store HTN prediction results linBuf: DWScanLinePtr _ NIL; -- Buffer to store LIN prediction results <<=================>> <> <<=================>> CompressPlate: PUBLIC SAFE PROCEDURE [ scanLen: CARDINAL, scanLineProc: ScanLineProc, putBitsProc: PutBitsProc] RETURNS [xPixels: CARDINAL, byteSize: LONG CARDINAL] = TRUSTED BEGIN <<=========>> <> <<=========>> nNibs: CARDINAL = 4; -- Number of nibbles in a word nRange: CARDINAL = 8; -- HTN predictor sample (bits) <> 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]; <> nibVal: ARRAY [0..15] OF INTEGER = [ 0, 3, 2, -4, 1, -5, -6, -7, 0, -9, -10, -11, -12, -13, -14, -15]; <> <> <= 0 THEN prediction output has only one bit on.>> <> <<>> <> <<>> <> iRAWPercent: INTEGER _ 67; iRAWCt: INTEGER _ 0; <> minNibPercent: INTEGER _ 1; minNibCt: INTEGER _ 0; <> 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; dummyLine2: 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 <> 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 <> first: CARDINAL _ nw1st * 2; last: CARDINAL; lastDWord: CARDINAL _ lastWord; kWord: CARDINAL; pvByte: CARDINAL _ 0; nLine: ScanLinePtr _ LOOPHOLE[nwLine]; nibCt _ 0; <> 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]]; <> 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 <> kWord: LONG CARDINAL; lWord, hWord: CARDINAL; iFirst _ MIN[nw1st, pv1st]; iLast _ MAX[nwLast, pvLast]; <> 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] _ 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] = <> 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 <> PutNibble[8 + nibTrn] ELSE { PutByte[Basics.BITAND[Basics.BITSHIFT[iRun, 2], 174B] + nibTrn]; iRun _ 0; }; END; -- Go10XXorA <<======>> <
> <> iRun _ iRun * nNibs * 2; <> 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)]; <> 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]}; <> IF iRun > 25 THEN {Go11ggggggabcd[]; LOOP; -- done with this nibble-- }; <> nibTrn _ nibVal[nibble]; IF nibTrn >= 0 THEN {Go10XXorA[]; LOOP; -- done with this nibble-- }; <> IF iRun > 1 THEN {Go11ggggggabcd[]; LOOP; -- done with this nibble-- }; <> PutByte[140B - (nibTrn + nibTrn) + iRun]; iRun _ 0; END; -- IF nibble = 0 ELSE ENDLOOP; -- every nibble <> iRun _ iRun + (nNibs - nibInd); ENDLOOP; -- every word END; -- GoENC <<============>> GoENCorRAW: PROCEDURE = BEGIN <> IF nwNibCt >= iRAWCt THEN GoRAW[] ELSE BEGIN <> linCount _ 0; encLines _ encLines + 1; PutByte[enc]; currLine _ LOOPHOLE[nwLine]; iFirst _ nw1st; iLast _ nwLast; GoENC[iRun]; END; END; -- GoENCorRAW <<===========>> GoLINorRAW: PROCEDURE = BEGIN <> IF linNibCt >= iRAWCt THEN GoRAW[] ELSE { <> 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 <> IF (linNibCt < htnNibCt) AND (linNibCt > 0) THEN GoLINorRAW[] ELSE { IF htnNibCt > iRAWCt THEN GoRAW[] ELSE { <> linCount _ 0; htnLines _ htnLines + 1; PutByte[htn]; iFirst _ nw1st; iLast _ MIN[nwLast + 1, lastWord]; currLine _ htnBuf; <> GoENC[iRun]; -- encode }; }; END; --GoLINorHTNorRAW <<============>> GoRAW: PROCEDURE = BEGIN <> 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}; <<>> <
> <<>> <> 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 <> pvNibCt _ nwNibCt; pv1st _ nw1st; pvLast _ nwLast; <> <> <> [nwNibCt, nw1st, nwLast, iRun] _ GetEstimateAndLimits[]; <<>> IF nwNibCt = 0 THEN blankLn _ blankLn + 1 ELSE BEGIN <> FlushBlankLines[]; <> IF nwNibCt < minNibCt THEN { GoENCorRAW[]; -- output current line in ENC or RAW mode LOOP; }; -- done with this line <> linNibCt _ -1; IF ((2 * ABS[nwNibCt - pvNibCt]) < nwNibCt) AND (linCount < maxLINCount) THEN BEGIN <> linNibCt _ GetLINPredictData[nwLine, pvLine]; <> IF linNibCt < minNibCt THEN { GoLINorRAW[]; LOOP; -- done with this line }; END; <> htnNibCt _ GetHTNPredictData[]; -- htnNibCt obtained <> <> <> 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 }; <> GoLINorRAW[]; END; ENDLOOP; -- every scan line <> 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 <<=====>> Initialize: PUBLIC SAFE PROCEDURE [] = TRUSTED BEGIN htnBuf _ NEW[ScanLine]; linBuf _ NEW[DWScanLine]; END; -- Initialize END...... LOG 14Sep84 - Okamoto - Creation 31Jan85 - Okamoto - Performance improvement by using double words. 28Feb85 - Okamoto - For blank page, xpixels is set one. 10Jul85 - castillo - copyright notice. <<>>