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]; 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 { 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. DXeroxCompressImpl.mesa Copyright (C) 1985, 1986 by Xerox Corporation. All rights reserved. last edited by castillo 10-Jul-85 9:57:58 Tim Diebert: December 1, 1986 9:48:48 am PST This module should be identical to XeroxCompress except the tool's output routine, NakedComment, is called to output stats. ================ GLOBAL VARIABLES ================ ================= PUBLIC PROCEDURES ================= ========= CONSTANTS ========= IMG code Mask array to get nibbles from a word 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 A limit representing the point at which to output a raster line in its raw form rather than in one of the encoded forms. 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. ========== ========== This routine will compute various limits that are used later in determining which prediction model to use. ========== This routine will compute htnNibCt which are used later in determining whethter HTN mode is feasible for the line. Get that last word. Had to add 2 since we are usually dealing with double words. Count the number of non-zero nibbles ========== 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 set the pointer of line used by encoding routines to pvLine (LIN XOR results are stored in linBuf) kWord _ linBuf[i] _ Basics.DBITXOR[nwLine[i], pvLine[i]]; ============ iRun passed as argument for efficiency reason ====== ====== Output if the form 10XXorA ====== Main of GoENC change running count of non-zero words to non-zero nibbles change iFirst and iLast to words indices nonZero Nibble obtained. Encode run length 11gggggg0000 case Determine Descriptor to be used for data nibble Descriptor determination requires nibble be evaluated Nibble has more than one bit on Encode using Type 'B short descriptor adjust for trailing zero nibbles of word ============ This routine will decide whether RAW mode or ENC mode is more feasible. Scan line to be encoded with no prediction =========== This routine will decide whether LIN mode or RAW mode is more feasible. Use LIN mode. Remember that pvLine was used as buffer for XORed bits ============ This routine is faced with a decision whether to go with LIN, HTN or RAW mode HTN mode seems most feasible iRun should remain the same. ============ Go RAW! ===== ===== ===== ===== Main of CompressPlate Change prediction estimate parameter from % to nibbles Set up predictor parameters from previous line IF scnLines = debugLine THEN Runtime.CallDebugger["Desired line encountered"L]; Compute estimate and limits for encoding this line Output deferred blank lines, if any See if short-cut estimate for encoding data can be used See if LIN mode is feasible get linNibCt for LIN mode Try short-cut estimate for LIN mode Short-cut method for LIN failed, see if HTN can be used Results from feasible prediction modes have been obtained. Use results to estimate most compressable mode to employ Try Raw or LIN mode Ensure at least one line is output ===== Κ2˜codešœ™KšœD™DKšœ,™,K™,—K˜šΟk ˜ Kš œœœœœ2˜rK˜—K˜šΟnœ˜Kšœ˜Kšœ˜Kšœœ˜Kšœ{™{—K˜˜Kšœ™Kšœ™Kšœ™KšœœΟc)˜EKšœœŸ)˜G—˜Kšœ™Kšœ™Kšœ™—˜šž œœœ œ˜&Kšœ œ7˜HKšœ œ œœ˜6Kšœ˜ K˜Kšœ ™ Kšœ ™ Kšœ ™ KšœœŸ˜4KšœœŸ˜5—˜Kšœ™KšœœŸ ˜Kšœœ Ÿ˜%KšœœŸ ˜KšœœŸ ˜KšœœŸ˜-Kšœœ Ÿ˜'K˜Kšœ œŸ%˜BKšœ œ œœ˜DKšœ%™%šœœ œœ˜$K˜AKšœŠ™ŠKšœF™FKšœB™B—Kšœ™K˜K™Kšœ)™)K™Kšœ:™:Kšœ œ˜šœœ˜Kšœx™x—Kšœœ˜šœ œ˜Kšœε™ε——˜Kšœ œœœ˜%K˜KšœœœŸ!˜KšœœŸ_˜}Kšœ œŸ˜4Kšœ œŸ˜7Kšœ œŸ@˜XKšœœŸ@˜WKšœœŸ˜3KšœœŸ?˜UKšœ œŸ"˜;Kšœ œŸ˜7Kšœ œŸ@˜XKšœŸ˜2KšœœŸ˜=Kšœ œŸ(˜?KšœŸ.˜GKšœŸ0˜JKšœœŸd˜‚Kšœ œŸ)˜