<> <> <> <> DIRECTORY XeroxCompress, Basics USING [bitsPerByte, bitsPerWord, BITAND, BITSHIFT, BITXOR, DoubleXor, HighByte, HighHalf, LongMult, LowByte, LowHalf], <> <> XeroxCompressImpl: PROGRAM IMPORTS Basics, Runtime, Space EXPORTS XeroxCompress = BEGIN OPEN XeroxCompress; <<>> <> <> <> wrdsInScanLine: CARDINAL = 256; dWrdsInScanLine: CARDINAL = wrdsInScanLine / 2; <> BitWrdIndex: TYPE = [0..wrdsInScanLine); ScanLine: TYPE = ARRAY [0..wrdsInScanLine) OF CARDINAL; ScanLineRef: TYPE = REF ScanLine; DWScanLine: TYPE = ARRAY [0..dWrdsInScanLine) OF LONG CARDINAL; DWScanLineRef: TYPE = REF DWScanLine; <> htnBuf: ScanLineRef ¬ NIL; -- Buffer to store HTN prediction results linBuf: DWScanLineRef ¬ NIL; -- Buffer to store LIN prediction results <> 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) <> 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: ScanLineRef ¬ NIL; -- Current scan line used by GoENC. <> <> 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 <> iFirst: CARDINAL ¬ 0; -- Index of first dword in currLine used by <> iRun: CARDINAL ¬ 0; -- Running count of zero words iLast: CARDINAL ¬ 0; -- Index of last dword in currLine used by <> 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 <> 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 <> nwLast: BitWrdIndex ¬ 0; -- Index to last non-zero dword in <> pvLine: DWScanLineRef ¬ NIL; -- Pointer to last scan line. If <> <> pvNibCt: INTEGER; -- non-zero nibble count in previous line pv1st: BitWrdIndex ¬ 0; -- Pointer to 1st non-zero dword in <> pvLast: BitWrdIndex ¬ 0; -- Pointer to last non-zero dword in <> 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; dummyLine2: 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] = { <> <> 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] = { <> <> first: CARDINAL ¬ nw1st * 2; last: CARDINAL; lastDWord: CARDINAL ¬ lastWord; kWord: CARDINAL; pvByte: CARDINAL ¬ 0; nLine: ScanLineRef ¬ 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 }; -- GetHTNPredictData GetLINPredictData: PROCEDURE [nwLine: DWScanLineRef, pvLine: DWScanLineRef] RETURNS [c: INTEGER] = { <> <> <> <> 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 <> 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] = { <> 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 <> PutNibble[8 + nibTrn] ELSE { PutByte[Basics.BITAND[Basics.BITSHIFT[iRun, 2], 174B] + nibTrn]; iRun ¬ 0; }; }; -- 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 { 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; }; -- IF nibble = 0 ELSE ENDLOOP; -- every nibble <> iRun ¬ iRun + (nNibs - nibInd); ENDLOOP; -- every word }; -- GoENC GoENCorRAW: PROCEDURE = { <> IF nwNibCt >= iRAWCt THEN GoRAW[] ELSE { <> linCount ¬ 0; encLines ¬ encLines + 1; PutByte[enc]; currLine ¬ LOOPHOLE[nwLine]; iFirst ¬ nw1st; iLast ¬ nwLast; GoENC[iRun]; }; }; -- GoENCorRAW GoLINorRAW: PROCEDURE = { <> 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 }; }; -- GoLINorRAW GoLINorHTNorRAW: PROCEDURE = { <> 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 }; }; }; --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}; <<>> <
> <<>> <> 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; IF scnLines = debugLine THEN Runtime.CallDebugger["Desired line encountered"L]; <> [nwNibCt, nw1st, nwLast, iRun] ¬ GetEstimateAndLimits[]; <<>> IF nwNibCt = 0 THEN blankLn ¬ blankLn + 1 ELSE { <> 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 { <> linNibCt ¬ GetLINPredictData[nwLine, pvLine]; <> IF linNibCt < minNibCt THEN { GoLINorRAW[]; LOOP; -- done with this line }; }; <> 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[]; }; 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; }; -- CompressPlate Initialize: PUBLIC PROCEDURE [] = { htnBuf _ NEW[ScanLine]; linBuf _ NEW[DWScanLine]; }; -- Initialize END. <<>> <> <<14Sep84 - Okamoto - Creation>> <<31Jan85 - Okamoto - Performance improvement by using double words.>> <<28Feb85 - Okamoto - For blank page, xpixels is set one.>> <<10Jul85 - castillo - copyright notice.>> <> <> < Basics>>