DIRECTORY Basics, CountedVM, PrincOps, PrincOpsUtils, Real, ImagerDither, ImagerPixelMap; ImagerDitherImpl: CEDAR PROGRAM IMPORTS Basics, CountedVM, PrincOpsUtils, ImagerPixelMap EXPORTS ImagerDither ~ BEGIN OPEN ImagerDither; bitsPerWord: NAT ~ Basics.bitsPerWord; MaxPackedColor: PUBLIC PROC [packing: PackedColorDesc] RETURNS [CARDINAL] ~ { totalBits: [0..16] ~ packing.redBits+packing.greenBits+packing.blueBits+packing.tileIndexBits; RETURN [Basics.BITSHIFT[1, totalBits]-1]; }; Pack1: PROC [a: CARDINAL, b: BYTE, bits: NAT] RETURNS [CARDINAL] ~ { RETURN [Basics.BITSHIFT[a, bits] + Basics.BITSHIFT[b, bits-8]]; }; Pack: PUBLIC PROC [red, green, blue: BYTE, packing: PackedColorDesc] RETURNS [PackedColor] ~ { totalBits: [0..16] ~ packing.redBits+packing.greenBits+packing.blueBits+packing.tileIndexBits; RETURN [Pack1[Pack1[Pack1[Pack1[0, red, packing.redBits], green, packing.greenBits], blue, packing.blueBits], 0, packing.tileIndexBits]]; }; Unpack1: PROC [a: CARDINAL, bits: NAT] RETURNS [CARDINAL, BYTE] ~ { max: CARDINAL ~ Basics.BITSHIFT[1, bits]-1; b: BYTE _ Basics.BITSHIFT[Basics.BITAND[a, max], 8-bits]; FOR k: NAT _ bits, 2*k UNTIL k >= 8 DO b _ b + Basics.BITSHIFT[b, -k]; ENDLOOP; RETURN [Basics.BITSHIFT[a, -bits], b]; }; Unpack: PUBLIC PROC [packed: PackedColor, packing: PackedColorDesc] RETURNS [red, green, blue: BYTE, tileIndex: CARDINAL] ~ { zero: [0..0] _ 0; [packed, tileIndex] _ Unpack1[packed, packing.tileIndexBits]; [packed, blue] _ Unpack1[packed, packing.blueBits]; [packed, green] _ Unpack1[packed, packing.greenBits]; [zero, red] _ Unpack1[packed, packing.redBits]; }; PackSequence: PUBLIC UNSAFE PROC [dest, red, green, blue: LONG POINTER TO RawWords, count: NAT, packing: PackedColorDesc] ~ UNCHECKED { totalBits: [0..bitsPerWord] ~ packing.redBits+packing.greenBits+packing.blueBits+packing.tileIndexBits; redBit0: NAT ~ bitsPerWord-totalBits; greenBit0: NAT ~ redBit0+packing.redBits; blueBit0: NAT ~ greenBit0+packing.greenBits; bbspace: PrincOps.BBTableSpace; bb: PrincOps.BitBltTablePtr ~ PrincOpsUtils.AlignedBBTable[@bbspace]; bb^ _ [ dst: [word: dest, bit: redBit0], dstBpl: bitsPerWord, src: [word: red, bit: bitsPerWord-8], srcDesc: [srcBpl[bitsPerWord]], width: packing.redBits, height: count, flags: [disjoint: TRUE] ]; PrincOpsUtils.LongZero[where: dest, nwords: count]; PrincOpsUtils.BITBLT[bb]; bb.dst.bit _ greenBit0; bb.src.word _ green; PrincOpsUtils.BITBLT[bb]; bb.dst.bit _ blueBit0; bb.src.word _ blue; PrincOpsUtils.BITBLT[bb]; }; PreDither: PUBLIC UNSAFE PROC [words: LONG POINTER TO RawWords, count: NAT, s: NAT _ 0, bits: NAT _ 8, fractionBits: NAT _ 4] ~ UNCHECKED { max: CARDINAL ~ Basics.BITSHIFT[1, bits]-1; maxFrac: CARDINAL ~ Basics.BITSHIFT[1, fractionBits]-1; mask: CARDINAL ~ max-maxFrac; d: CARDINAL _ Basics.BITAND[Basics.BITAND[s, maxFrac]*16+s, maxFrac]; FOR j: NAT IN [0..count) DO c: CARDINAL ~ words[j]+d; words[j] _ Basics.BITAND[Basics.BITAND[c, mask] - Basics.BITSHIFT[c, -bits], max]; d _ Basics.BITAND[d+7, maxFrac]; ENDLOOP; }; Dither: PUBLIC UNSAFE PROC [destLine: LONG POINTER TO RawBytes, start, count: NAT, packed: LONG POINTER TO RawWords, sTile, fTile: CARDINAL, table: Table] ~ UNCHECKED { sTileSize: NAT ~ table.sTileSize; fTileSize: NAT ~ table.fTileSize; sTileComp: NAT ~ (sTile MOD sTileSize)*fTileSize; lastTileIndex: NAT ~ sTileComp + (fTileSize-1); tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; tileIndex: CARDINAL _ sTileComp + (fTile MOD fTileSize); IF destLine = NIL THEN ERROR; FOR j: NAT IN [0..count) DO destLine[start+j] _ tableBase[packed[j]+tileIndex]; tileIndex _ IF tileIndex # lastTileIndex THEN tileIndex+1 ELSE sTileComp; ENDLOOP; }; WordDither: PUBLIC UNSAFE PROC [destLine: LONG POINTER TO RawWords, start, count: NAT, packed: LONG POINTER TO RawWords, sTile, fTile: CARDINAL, table: Table] ~ UNCHECKED { sTileSize: NAT ~ table.sTileSize; fTileSize: NAT ~ table.fTileSize; sTileComp: NAT ~ (sTile MOD sTileSize)*fTileSize; lastTileIndex: NAT ~ sTileComp + (fTileSize-1); tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; tileIndex: CARDINAL _ sTileComp + (fTile MOD fTileSize); IF destLine = NIL THEN ERROR; FOR j: NAT IN [0..count) DO destLine[start+j] _ tableBase[packed[j]+tileIndex]; tileIndex _ IF tileIndex # lastTileIndex THEN tileIndex+1 ELSE sTileComp; ENDLOOP; }; bytesPerWord: NAT ~ Basics.bytesPerWord; Mod: PROC [a, b: CARDINAL] RETURNS [CARDINAL] ~ INLINE { RETURN [a MOD b]; }; DitherConstant: PUBLIC UNSAFE PROC [destLine: LONG POINTER TO RawBytes, start, count: NAT, packed: PackedColor, sTile, fTile: CARDINAL, table: Table] ~ UNCHECKED { sTileSize: NAT ~ table.sTileSize; fTileSize: NAT ~ table.fTileSize; sTileComp: NAT ~ Mod[sTile, sTileSize]*fTileSize; lastTileIndex: NAT ~ sTileComp + (fTileSize-1); tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; tileIndex: CARDINAL _ sTileComp + Mod[fTile, fTileSize]; initCount: CARDINAL _ count; longCopyRipple: CARDINAL _ 0; IF bytesPerWord=2 AND count > 6 THEN { SELECT fTileSize FROM 3 => {initCount _ 6 + (start MOD 2); longCopyRipple _ 3}; 4 => {initCount _ 4 + (start MOD 2); longCopyRipple _ 2}; ENDCASE => NULL; }; IF destLine = NIL THEN ERROR; FOR j: NAT IN [start..start+initCount) DO destLine[j] _ tableBase[packed+tileIndex]; tileIndex _ IF tileIndex # lastTileIndex THEN tileIndex+1 ELSE sTileComp; ENDLOOP; IF longCopyRipple # 0 THEN { words: CARDINAL ~ (count-initCount)/bytesPerWord; residual: [0..1] ~ count-initCount-bytesPerWord*words; startAddr: LONG POINTER TO WORD ~ LOOPHOLE[destLine, LONG POINTER TO WORD] + (start+initCount)/bytesPerWord; PrincOpsUtils.LongCopy[from: startAddr-longCopyRipple, nwords: words, to: startAddr]; IF residual # 0 THEN destLine[start+count-1] _ destLine[start+count-1-fTileSize]; }; }; WordDitherConstant: PUBLIC UNSAFE PROC [destLine: LONG POINTER TO RawWords, start, count: NAT, packed: PackedColor, sTile, fTile: CARDINAL, table: Table] ~ UNCHECKED { sTileSize: NAT ~ table.sTileSize; fTileSize: NAT ~ table.fTileSize; sTileComp: NAT ~ Mod[sTile, sTileSize]*fTileSize; lastTileIndex: NAT ~ sTileComp + (fTileSize-1); tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; tileIndex: CARDINAL _ sTileComp + Mod[fTile, fTileSize]; initCount: CARDINAL _ MIN[count, fTileSize]; IF destLine = NIL THEN ERROR; FOR j: NAT IN [start..start+initCount) DO destLine[j] _ tableBase[packed+tileIndex]; tileIndex _ IF tileIndex # lastTileIndex THEN tileIndex+1 ELSE sTileComp; ENDLOOP; IF count > initCount THEN { startAddr: LONG POINTER TO WORD ~ @(destLine[start+initCount]); PrincOpsUtils.LongCopy[from: startAddr-fTileSize, nwords: count-initCount, to: startAddr]; }; }; CreateTable: PUBLIC PROC [packing: PackedColorDesc, sTileSize: NAT _ 4, fTileSize: NAT _ 4] RETURNS [Table] ~ { maxPackedColor: CARDINAL ~ MaxPackedColor[packing]; tileSize: NAT ~ Basics.BoundsCheck[sTileSize*fTileSize-1, Basics.BITSHIFT[1, packing.tileIndexBits]]; RETURN [NEW[TableRep _ [ packing: packing, maxPackedColor: maxPackedColor, sTileSize: sTileSize, fTileSize: fTileSize, space: CountedVM.SimpleAllocate[(INT[maxPackedColor]+1)/Basics.bytesPerWord] ]]]; }; ShowTable: PROC [table: Table, pm: ImagerPixelMap.PixelMap] ~ TRUSTED { t: ImagerPixelMap.PixelMap ~ ImagerPixelMap.CreateFrameBuffer[pointer: table.space.pointer, words: table.space.words, lgBitsPerPixel: 3, rast: 2, lines: 4096*4, ref: table.space]; pm _ pm.ShiftMap[-40, -60].Clip[[0,0,324,324+82]]; pm.Fill[[0,0,324,324+82], 0]; FOR r: NAT IN [0..16) DO sr: NAT _ (r/4) * 81 + 1; fr: NAT _ (r MOD 4) * 81 + 1; FOR g: NAT IN [0..16) DO s: NAT _ sr + g*5; FOR b: NAT IN [0..16) DO f: NAT _ fr + b*5; pm.Transfer[t.ShiftMap[-((r*16+g)*16+b)*4, 0].Clip[[0,0,4,4]].ShiftMap[s,f]]; ENDLOOP; ENDLOOP; ENDLOOP; pm _ pm.ShiftMap[0, -324].Clip[[0,0,324,82]]; FOR i: NAT IN [0..32) DO s: NAT _ i * 10 + 2; FOR j: NAT IN [0..8) DO f: NAT _ j * 10 + 1; pm.Fill[[s, f, 9, 9], i*8+j]; ENDLOOP; ENDLOOP; }; InitTable: PUBLIC PROC [table: Table, map: LIST OF MapEntry, scaleMap: NAT] ~ { tableBytes: INT ~ INT[table.space.words]*Basics.bytesPerWord; redMap: ARRAY ChannelValue OF INTEGER _ ALL[NAT.LAST]; greenMap: ARRAY ChannelValue OF INTEGER _ ALL[NAT.LAST]; blueMap: ARRAY ChannelValue OF INTEGER _ ALL[NAT.LAST]; InitMaps: PROC ~ { FOR p: LIST OF MapEntry _ map, p.rest UNTIL p=NIL DO redMap[p.first.mapIndex] _ p.first.red*scaleMap; greenMap[p.first.mapIndex] _ p.first.green*scaleMap; blueMap[p.first.mapIndex] _ p.first.blue*scaleMap; ENDLOOP; }; Closest: PROC [red, green, blue: INTEGER, guess: ChannelValue] RETURNS [ChannelValue] ~ { best: ChannelValue _ 0; bestDistSqr: LONG CARDINAL _ LAST[LONG CARDINAL]; bestDistBound: NAT _ LAST[NAT]; Try: PROC [a: ChannelValue, r, g, b: INTEGER] ~ INLINE { absRed, absGreen, absBlue: CARDINAL; distSqr: LONG CARDINAL; IF (absRed_ABS[redMap[a]-red]) <= bestDistBound AND (absGreen_ABS[greenMap[a]-green]) <= bestDistBound AND (absBlue_ABS[blueMap[a]-blue]) <= bestDistBound AND (distSqr_Basics.LongMult[absRed,absRed] + Basics.LongMult[absGreen,absGreen] + Basics.LongMult[absBlue,absBlue]) < bestDistSqr THEN { bestDistBound _ absRed+absGreen+absBlue; bestDistSqr _ distSqr; best _ a; }; }; Try[guess, redMap[guess], greenMap[guess], blueMap[guess]]; FOR p: LIST OF MapEntry _ map, p.rest UNTIL p=NIL OR bestDistSqr=0 DO mapIndex: ChannelValue ~ p.first.mapIndex; Try[mapIndex, redMap[mapIndex], greenMap[mapIndex], blueMap[mapIndex]]; ENDLOOP; RETURN [best]; }; ComputeClosestColors: PROC ~ TRUSTED { delta: NAT ~ Basics.BITSHIFT[1, table.packing.tileIndexBits]; tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; guess: ChannelValue _ 0; maxPackedColor: CARDINAL ~ table.maxPackedColor; IF maxPackedColor >= tableBytes THEN ERROR; IF tableBase = NIL THEN ERROR; FOR c: INT _ 0, c + delta UNTIL c > maxPackedColor DO packed: CARDINAL ~ c; r, g, b: ColorValue; [r, g, b, ----] _ Unpack[packed, table.packing]; tableBase[packed] _ guess _ Closest[r, g, b, guess]; ENDLOOP; }; ClosestTabulated: PROC [red, green, blue: INTEGER] RETURNS [ChannelValue] ~ TRUSTED { tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; r: ColorValue ~ MIN[MAX[red, 0], ColorValue.LAST]; g: ColorValue ~ MIN[MAX[green, 0], ColorValue.LAST]; b: ColorValue ~ MIN[MAX[blue, 0], ColorValue.LAST]; packed: CARDINAL ~ Pack[r, g, b, table.packing]; RETURN [tableBase[packed]] }; ComputeTiles: PROC ~ TRUSTED { delta: NAT ~ Basics.BITSHIFT[1, table.packing.tileIndexBits]; tileSize: NAT ~ table.sTileSize*table.fTileSize; maxPackedColor: CARDINAL ~ table.maxPackedColor; tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; FOR c: INT _ 0, c + delta UNTIL c > maxPackedColor DO packed: CARDINAL ~ c; r0, g0, b0, r, g, b: INTEGER; [r0, g0, b0, ----] _ Unpack[packed, table.packing]; r _ r0; g _ g0; b _ b0; FOR i: NAT IN [1..tileSize) DO close: ChannelValue ~ ClosestTabulated[r, g, b]; IF LONG[packed]+i >= tableBytes THEN ERROR; tableBase[packed+i] _ close; r _ r - redMap[close] + r0; g _ g - greenMap[close] + g0; b _ b - blueMap[close] + b0; ENDLOOP; ENDLOOP; }; SortTiles: PROC ~ TRUSTED { delta: NAT ~ Basics.BITSHIFT[1, table.packing.tileIndexBits]; tileSize: NAT ~ table.sTileSize*table.fTileSize; maxPackedColor: CARDINAL ~ table.maxPackedColor; tableBase: LONG POINTER TO RawBytes ~ table.space.pointer; intensity: ARRAY BYTE OF REAL _ ALL[Real.TrappingNaN]; inverseOrder: PACKED ARRAY BYTE OF BYTE _ GetTileOrder[table.sTileSize, table.fTileSize]; FOR p: LIST OF MapEntry _ map, p.rest UNTIL p=NIL DO intensity[p.first.mapIndex] _ p.first.red*0.30 + p.first.green*0.59 + p.first.blue*0.11; ENDLOOP; FOR c: INT _ 0, c + delta UNTIL c > maxPackedColor DO packed: CARDINAL ~ c; At: PROC [j: NAT] RETURNS [CARDINAL] ~ CHECKED INLINE {RETURN [packed+inverseOrder[j]]}; IF c >= trapVal THEN {trapVal _ c}; FOR i: NAT IN [1..tileSize) DO channelI: BYTE ~ tableBase[packed+inverseOrder[i]]; intensityI: REAL ~ intensity[channelI]; j: NAT _ i; WHILE j#0 AND intensityI < intensity[tableBase[At[j-1]]] DO tableBase[At[j]] _ tableBase[At[j-1]]; j _ j-1; ENDLOOP; tableBase[At[j]] _ channelI; ENDLOOP; ENDLOOP; }; InitMaps[]; ComputeClosestColors[]; ComputeTiles[]; SortTiles[]; }; trapVal: INT _ 0; sSizeSpecial: NAT _ 4; fSizeSpecial: NAT _ 4; specialTileOrder: REF ARRAY [0..20) OF NAT _ NEW[ARRAY [0..20) OF NAT _ [ 0, 14, 3, 13, 11, 5, 8, 6, 12, 2, 15, 1, 7, 9, 4, 10, 0, 0, 0, 0 ]]; tileDelta: NAT _ 7; GetTileOrder: PROC [sTileSize, fTileSize: NAT] RETURNS [inverseOrder: PACKED ARRAY BYTE OF BYTE] ~ { tileSize: NAT ~ sTileSize*fTileSize; IF sTileSize = sSizeSpecial AND fTileSize = fSizeSpecial THEN { FOR i: NAT IN [0..tileSize) DO inverseOrder[specialTileOrder[i]] _ i ENDLOOP; } ELSE { j: NAT _ 0; FOR i: NAT IN [0..tileSize) DO inverseOrder[j] _ i; j _ (j + tileDelta) MOD tileSize; ENDLOOP; }; }; END. ImagerDitherImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Michael Plass, August 2, 1985 9:51:16 am PDT May want to special case for a certain value of b here. For debugging the table builder; pm should describe the eight bpp color display. Κε˜šœ™Icodešœ Οmœ1™