{
File name: CompressAssist.mc
Description: Special M'Code for data compression. (originally for DASH project)
Author: KXI
Created: 12-Nov-85 9:12:36
Last Edited:
RCH 21-Jul-86 16:19:51: Cmmented PushByte, PushByteToWordBoundary
KXI 31-Jan-86 15:42:01: fix double word increment bug in @PB and @PBWB.
KXI 30-Jan-86 19:03:36: use L2 instead of L3 in @PB and @PBWB. fix even odd confusion.
KXI 30-Jan-86 14:55:59: add comments {each MCode definition describing by Mesa}
KXI 29-Jan-86 15:25:26: fix page end operations in @NMAD.
KXI 22-Jan-86 14:55:24: change page end operations in @NMAD.
KXI 14-Jan-86 18:14:40: add comments, remove L0 ← L0.NextMatchAndDiff, RLMFRet[L0.NextMatchAndDiff] and L0 ← L0.CLR
AEF 28-Dec-85 15:19:10: Change - to xor, fix CLR
AEF 27-Dec-85 20:08:33: Fix last word of page problems
AEF 27-Dec-85 12:30:31: Remove stack pushes
AEF 27-Dec-85 11:43:40: Remove ref bit check, change names to abbreviations
AEF 26-Dec-85 17:20:38: Change dispatches to branches in non-dup loop
AEF 26-Dec-85 15:38:51: Change TOS to RH reg in CLR, change 99 to FF, use NxtInstc1 label
KXI 26-Dec-85 10:12:44: bugs in NextMatchAndDiff about page end processings..
KXI 23-Dec-85 13:01:27: The definition of @NextMatchAndDiff was changed..
If state = **FF at the begginig then RETURN[(startVA + 100) AND FFFF00, (startVA + 100) AND FFFF00]
KXI 20-Dec-85 14:32:27: remove PC ← PC + 1. change L1 value for Map.
KXI 19-Dec-85 16:32:57: change assignment of ESC Alpha number for each byte codes.}
{******************************************************************************
* NMAD: NextMatchAndDiff ESC + ['b][H]
******************************************************************************}
{ TOS = STK[0] = minMatchCount
STK = STK[-1] = startVA.High
STK[-2] = startVA.Low
Assumption: A page which startVA points to is resident, in other words is not swappable. and map flags are alredy set as (r,d,wp) = (1,*,*) {readOK}.So This byte code does not need to check map flags.}
@NMAD: at[ 4, 10, ESC3n],
rhCurRefWordVA ← STK, pop, c1;
rCurRefWordVA ← STK, c2;
rTopOfCurrentPg.Low ← rCurRefWordVA and ~00FF{FF00}, c3;
Map ← Q ← [rhCurRefWordVA, rCurRefWordVA], L1 ← L1.PushDec2, c1;
rTopOfNextPg.Low ← rTopOfCurrentPg.Low + 0FF + 1, c2;
rCurRefWordRA ← rhCurRefWordRA ← MD, c3;
MAR ← rCurRefWordRA ← [rhCurRefWordRA, Q+0], c1;
Noop, c2;
rWordA ← MD, c3;
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], c1;
Noop, DISP2[CheckCr]{We are sure that bit 15 = 0.}, c2;
rWordB ← MD, c3, at[0,4,CheckCr];
{ -- not in duplicate mode.}
NMAD.NotDupLoop:
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], c1;
NotDupLoop.1C2:
[]← rWordA xor rWordB, ZeroBr, L1 ← 9, BRANCH[$, NotDup.NextIsPgEnd0, 1],c2;
rWordA ← MD{nextRefWord}, BRANCH[$, NMAD.Dup0], c3;
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], c1;
NotDupLoop.2C2:
[]← rWordB xor rWordA, ZeroBr, L1 ← 0D, BRANCH[$, NotDup.NextIsPgEnd1, 0D],c2;
rWordB ← MD{nextRefWord}, BRANCH[NMAD.NotDupLoop, NMAD.Dup1], c3;
{ -- in duplicate mode.}
{ calculate and save dupStartVA value.}
NMAD.Dup0: {here L1 = 2}
rDupStartVA.lowByte ← rCurRefWordRA and 00FF, GOTO[.Dup.a], c1;
NMAD.Dup1: {here L1 = 6}
rDupStartVA.lowByte ← rCurRefWordRA and 00FF, GOTO[.Dup.a], c1;
.Dup.a:
rDupStartVA.lowByte{00,,**} ← rDupStartVA.lowByte - 2{adjust}, L1Disp,c2;
STK{dupStartVA.Low} ← rTopOfCurrentPg.Low or rDupStartVA.lowByte{00,,**},
BRANCH[DupLoop.2C1, DupLoop.1C1, 0B],c3;
NMAD.DupLoop:
DupLoop.1C1:
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], c1;
[]← rWordA xor rWordB, ZeroBr, BRANCH[$, Dup.NextIsPgEnd0, 1], c2;
rWordA ← MD{nextRefWord}, BRANCH[NMAD.EndOfDup0, $], c3;
DupLoop.2C1:
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], c1;
[]← rWordB xor rWordA, ZeroBr, BRANCH[$, Dup.NextIsPgEnd1, 1], c2;
rWordB ← MD{nextRefWord}, BRANCH[NMAD.EndOfDup1, NMAD.DupLoop], c3;
{**** End of Dup Check ****}
NMAD.EndOfDup0:{here it is sure that rCurRefWordRA # **00H}
Q ← rDupStartVA.lowByte{00,,**}+TOS{minMatchCount}+1{adjust}, c1;
[]← rCurRefWordRA{curRefWord+1} - Q, PgCarryBr, c2;
rTemp{00,,**} ← rCurRefWordRA and 00FF, BRANCH[NMAD.CancelDups0{<}, NMAD.OKDups0{>=}],c3;
NMAD.CancelDups0:
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], GOTO[NotDupLoop.2C2],c1;
NMAD.OKDups0: {RETURN[dupStartVA, curRefWordVA], here dupStartVA is already in stack.}
Dup..OKDup.a: rTemp ← rTemp{00,,**} - 1{adjust}, push, c1;
.OKDups1.a:
TOS ← STK{dupStartVA.High=curRefWordVA.High}, push, IBDisp, c2;
STK{curRefWordVA.low} ← rTopOfCurrentPg.Low or rTemp{00,,**}, DISPNI[OpTable],c3;
NMAD.EndOfDup1:{here it is sure that rCurRefWordRA # **00H}
Q ← rDupStartVA.lowByte{00,,**}+TOS{minMatchCount}+1{adjust}, c1;
[]← rCurRefWordRA{curRefWord+1} - Q, PgCarryBr, c2;
rTemp{00,,**} ← rCurRefWordRA and 00FF, BRANCH[NMAD.CancelDups1{<}, NMAD.OKDups1{>=}],c3;
NMAD.CancelDups1:
MAR ← rCurRefWordRA ← [rhCurRefWordRA, rCurRefWordRA+1], GOTO[NotDupLoop.1C2],c1;
NMAD.OKDups1:{RETURN[dupStartVA, curRefWordVA], here dupStartVA is already in stack.}
rTemp ← rTemp{00,,**} - 1{adjust}, push, GOTO[.OKDups1.a], c1;
{**** Page End processing ****}
{** from Initial Mode **}
{NMAD.PgEnd: start = **FFH}{RETURN[(startVA + 100) AND FFFF00, (startVA + 100) AND FFFF00]}
STK ← rTopOfNextPg.Low, ZeroBr, push, c3, at[2,4,CheckCr];
NotDup..NotDupPgEnd:{RETURN[(startVA + 100) AND FFFF00, (startVA + 100) AND FFFF00]}
Dup..CancelDup.PgEnd:
.PgEnd.C1:
TOS ← STK{startVA.High}, BRANCH[$, .PgEnd.a.Cr], c1;
IBDisp, push, c2;
.PgEnd.C3:
STK ← rTopOfNextPg.Low, DISPNI[OpTable], c3;
.PgEnd.a.Cr:
TOS ← TOS{startVA.High} + 1, c2;
STK ← TOS{startVA.High+1}, GOTO[.PgEnd.C1], c3;
{** from NotDup Mode **}
NotDup.NextIsPgEnd0: {here we have to complete the last 2-words comparing..}
STK ← Q ← rTopOfNextPg.Low, ZeroBr, push, BRANCH[NotDup..NotDupPgEnd, NotDup..DupPgEnd],c3;
NotDup.NextIsPgEnd1: {here we have to complete the last 2-words comparing..}
STK ← Q ← rTopOfNextPg.Low, ZeroBr, push, BRANCH[NotDup..NotDupPgEnd, NotDup..DupPgEnd],c3;
NotDup..DupPgEnd: {RETURN[(startVA AND FFFF00) + 0FEH, (startVA + 100) AND FFFF00], here StartVA.High is already in stack.}
Dup.NotDupPgEnd.DupOK:
Q ← Q{rTopOfNextPg.Low} - 2, pop, CANCELBR[$, 1], c1;
STK{dupStartVA.low} ← Q, c2;
[] ← rTopOfNextPg.Low, ZeroBr, push, c3;
TOS ← STK{startVA.High}, BRANCH[NotDup..DupPgEnd.NoCr, NotDup..DupPgEnd.Cr],c1;
NotDup..DupPgEnd.Cr:
Dup..DupPgEnd.Cr:
TOS ← TOS{startVA.High} + 1, IBDisp, push, GOTO[.PgEnd.C3], c2;
NotDup..DupPgEnd.NoCr:
Dup..DupPgEnd.NoCr:
IBDisp, push, GOTO[.PgEnd.C3], c2;
{** from Dup Mode **}
Dup.NextIsPgEnd0: {here we have to complete the last 2-words comparing..}
[] ← rTopOfNextPg.Low, ZeroBr, push, BRANCH[Dup..NotDupPgEnd, Dup..DupPgEnd],c3;
Dup.NextIsPgEnd1: {here we have to complete the last 2-words comparing..}
[] ← rTopOfNextPg.Low, ZeroBr, push, BRANCH[Dup..NotDupPgEnd, Dup..DupPgEnd],c3;
Dup..DupPgEnd: {RETURN[dupStartVA, (startVA + 100) AND FFFF00], here dupStartVA is already in stack.}
TOS ← STK{startVA.High}, BRANCH[Dup..DupPgEnd.NoCr, Dup..DupPgEnd.Cr],c1;
Dup..NotDupPgEnd:{here rCurRefWordRA = **00H.}
[] ← rDupStartVA.lowByte{00,,**}+TOS{minMatchCount}+1{adjust}, PgCarryBr, CANCELBR[$, 1],c1;
pop{adjust}, BRANCH[..OKDup{>=}, ..CancelDup{<}], c2;
..OKDup: {RETURN[dupStartVA, (startVA AND FFFF00) + 0FFH]}
rTemp{00,,**} ← 0FF+1{this value will be decrement 1 at Dup..OKDup.a:}, GOTO[Dup..OKDup.a],c3;
..CancelDup: {RETURN[(startVA + 100) AND FFFF00, (startVA + 100) AND FFFF00]}
STK ← rTopOfNextPg.Low, ZeroBr, push, GOTO[Dup..CancelDup.PgEnd],c3;
{******************************************************************************
* PB: PushByte ESC + ['b][H]
******************************************************************************}
{ TOS = STK[0] = [00,,byte]
STK = STK[-1] = odd
STK[-2] = addr.high
STK[-3] = addr.low}
{@PB: at[5, 10, ESC3n],
rEvenOdd ← STK{odd}, pop, ZeroBr, c1;
L2 ← 0, BRANCH[PB.Odd, PB.Even], c2;
PB.Odd:
rByteMask ← ~0FF{FF00}, GOTO[PB.a],{odd => L2=0}, c3;
PB.Even:
rByteMask ← 0FF, GOTO[PB.a],{even => L2=1}, c3;}
{PB.a:
PB.PBWB:{L2=0 from @PBWB}
rByte{byte,,00} ← TOS{00,,byte} LRot8, c1;
rhTT ← STK{addr.high}, fZpop, c2;
TT{addr.low} ← STK{addr.low}, c3; }
{PB.Map:
Map ← Q ← [rhTT,TT], L0 ← L0.PushByte, c1;
L1 ← L1.Push2Dec2, c2;
Rx ← rhRx ← MD, XWtOKDisp, c3;
MAR ← [rhRx, Q+0], BRANCH[PB.WrNotOK, PB.WrOK,0D],c1, WLMFRet[L0.PushByte];}
{PB.WrNotOK:
CALL[WLMapFix],c2;
{sub.WLMapFix return to "WLMFRet[L0.PushByte]"}}
{PB.WrOK:
Rx ← Q, L2Disp{odd => L2=0, even => L2=1}, c2;
rData ← rByteMask and MD, DISP4[EvenOdd], c3;}
{PB.Even1:}
{PB.END:
MAR ← [rhRx, Rx+0], c1, at[1,10, EvenOdd];
MDR ← rByte and rData, push, IBDisp, c2;
TOS ← rEvenOdd xor 1, DISPNI[OpTable], c3;}
{{PB.Odd1:}
Q{addr.low+1} ← TT{addr.low} + 1, CarryBr, c1, at[0,10, EvenOdd];
STK{addr.low+1} ← Q, push, BRANCH[PB.NotCr, PB.Cr],c2; }
{PB.NotCr:
rByte{00,,byte} ← TOS{00,,byte}, GOTO[PB.END], c3;}
{PB.Cr:
Q ← STK{addr.high}, c3;
Q{addr.high+1} ← Q + 1, c1;
STK{addr.high+1} ← Q, GOTO[PB.NotCr], c2;}
{******************************************************************************
* PBWB: PushByteToWordBoundary ESC + ['b][H]
******************************************************************************}
{ TOS = STK[0] = [00,,byte]
STK = STK[-1] = odd
STK[-2] = addr.high
STK[-3] = addr.low}
{@PBWB: at[6, 10, ESC3n],
rEvenOdd ← STK, fZpop, L2 ← 0, ZeroBr, c1;
rhTT ← STK{addr.high}, fZpop, BRANCH[PBWB.Odd, PBWB.Even], c2;}
{PBWB.Odd:
rByteMask ← ~0FF{FF00}, push, GOTO[PB.PBWB], c3;{here L2=0}}
{PBWB.Even:
TT{addr.low} ← STK{addr.low}, c3;
Map ← Q ← [rhTT,TT], L0 ← L0.PushByteToWB, c1;
rTemp{addr.low+1} ← TT{addr.low} + 1, L1 ← L1.Push2Dec2, c2;
Rx ← rhRx ← MD, XWtOKDisp, c3;
MAR ← [rhRx, Q+0], BRANCH[PBWB.WrNotOK, PBWB.WrOK,0D],c1, WLMFRet[L0.PushByteToWB];}
{PBWB.WrNotOK:
CALL[WLMapFix],c2;
{sub.WLMapFix return to "WLMFRet[L0.PushByteToWB]"}}
{PBWB.WrOK:
MDR ← TOS{00,,byte}, c2;
STK ← rTemp{addr.low+1}, push, ZeroBr, c3;
Q ← STK{addr.high}, BRANCH[PBWB.NotCr,PBWB.Cr], c1;}
{PBWB.NotCr:
TOS{addr.high} ← Q, IBDisp, GOTO[PBWB.END], c2;}
{PBWB.Cr:
TOS{addr.high+1} ← Q + 1, IBDisp, GOTO[PBWB.END], c2;}
{PBWB.END:
STK ← TOS{addr.high+1}, TOS ← 0{FALSE}, DISPNI[OpTable], c3;}
{******************************************************************************
* CLR: Clear ESC + ['b][H]
******************************************************************************}
{ TOS = STK[0] = destHi
STK = STK[-1] = destLow
Assumption: A page which dest points to is resident, in other words is not swappable. and map flags are alredy set as (r,d,wp) = (1,1,0) {writeOK}. So This byte code does not need to check map flags.}
@CLR: at[7, 10, ESC3n],
rDestVA ← TOS {destHi}, c1;
rhDestVA ← rDestVA LRot0, c2;
rDestVA ← STK{destLow}, pop, c3;
Map ← Q ← [rhDestVA, rDestVA], c1;
Noop, c2;
rDestRA ← rhDestRA ← MD, c3;
MAR ← rDestRA ← [rhDestRA, Q+0], GOTO[CLR.Loop.C2], c1;
CLR.Loop:
MAR ← rDestRA ← [rhDestRA, rDestRA+1], c1;
CLR.Loop.C2:
MDR ← 0, BRANCH[$, CLR.End, 1], c2;
Noop, GOTO[CLR.Loop], c3;
CLR.End:
TOS ← STK{STK[-2]}, pop, GOTO[NxtInstc1], {in Refill} c3;
{NxtInstc1: Noop, c1;
IBDispOnly: IBDisp, c2;
DISPNIonly: DISPNI[OpTable], c3;}
{ ****** M'Code definitions {describibg by Mesa} ****** }
{-- MesaCompressAssistImpl.mesa
-- Revised by CharlieLevy: 7-Nov-85 20:24:04
-- Owner: CharlieLevy
-- Copyright (C) Xerox Corporation 1985. All rights reserved.
DIRECTORY
MesaCompressAssist, Environment, Inline;
MesaCompressAssistImpl: PROGRAM
EXPORTS MesaCompressAssist =
BEGIN OPEN MesaCompressAssist;
-- Pack Data Structure:
-- Signals and Errors:
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- Public Operations
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
NextMatchAndDiff: PUBLIC PROC [start: LONG POINTER, matchCount:[2..7]]
RETURNS [nextMatch, nextDiff: LONG POINTER] =
BEGIN
lptCur: LONG POINTER;
bvInDup: BOOLEAN;
wordCur: WORD;
lptDupStart, lptNextPage: LONG POINTER;
bvInDup ← FALSE; -- start out presuming in difference mode
lptNextPage ← start + 256 - (LOOPHOLE[start, LONG CARDINAL] MOD 256);
-- default to start of next page, client must check for reasonableness
wordCur ← start↑; -- the first word in the difference string
lptCur ← start + 1;
DO
IF wordCur # lptCur↑ THEN -- compare the current and new words
BEGIN -- two words are unequal
IF bvInDup THEN
BEGIN -- bvInDup
IF (lptCur - lptDupStart >= matchCount) THEN
RETURN [lptDupStart, lptCur] -- enough of a match to return results
ELSE
bvInDup ← FALSE; -- cancel dup mode because two words are unequal
END; -- bvInDup
wordCur ← lptCur↑; -- set new wordCur in case we haven't returned
END -- of two words are unequal
ELSE
BEGIN -- two words are equal
IF bvInDup = FALSE THEN -- (if in dup mode and words are equal, do nothing)
BEGIN -- we just made a transition to possible duping
bvInDup ← TRUE; -- we are now in possible duping mode
lptDupStart ← lptCur - 1; -- and here's where that word run starts
END; -- transition to possible duping
END; -- of two words are equal
lptCur ← lptCur + 1; -- bump pointer for next time
IF lptCur = lptNextPage THEN RETURN [IF bvInDup THEN lptDupStart ELSE lptNextPage, lptNextPage];
-- bouncing off end of page
-- client will inspect to see if large enough match at page fault, if he chooses
ENDLOOP;
END; -- of NextMatchAndDiff
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
PushByte: PUBLIC PROC [bPtrOld: BPtr, byte: Environment.Byte] RETURNS [bPtrNew: BPtr]=
BEGIN
IF bPtrOld.odd THEN
BEGIN
bPtrOld.adrs↑.low ← byte;
RETURN [[bPtrOld.adrs + 1, FALSE]];
END
ELSE
BEGIN
bPtrOld.adrs↑.high ← byte;
RETURN [[bPtrOld.adrs, TRUE]];
END;
END; -- of PushByte
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
PushByteToWordBoundary: PUBLIC PROC [bPtrOld: BPtr, byte: Environment.Byte] RETURNS [bPtrNew: BPtr]=
BEGIN
IF NOT bPtrOld.odd THEN bPtrOld.adrs↑.high ← 0;-- needs a NOP
bPtrOld.adrs↑.low ← byte; -- in either case
RETURN [[bPtrOld.adrs + 1, FALSE]]; -- in either case
END; -- of PushByteToWordBoundary
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
Clear: PUBLIC PROC [start: LONG POINTER] =
BEGIN
-- this should be faster than using Inline.LongCOPY[]
lptCur, lptNextPage: LONG POINTER;
lptNextPage ← start + 256 - (LOOPHOLE[start, LONG CARDINAL] MOD 256);
-- default to start of next page, client must check for reasonableness
lptCur ← start;
DO
lptCur↑ ← 0;
lptCur ← lptCur + 1; -- bump pointer for next time
IF lptCur = lptNextPage THEN RETURN; -- bouncing off end of page
ENDLOOP;
END; -- of Clear
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- Private Procedures
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
-- Mainline Code
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
END. -- of CompressAssistImpl
LOG
15-Oct-85 CharlieLevy created module
22-Oct-85 CL started using page faults rather than endPlusOne
25-Oct-85 CL added PushByte and PushByteToWordBoundary
28-Oct-85 CL made faster running and desk checked
5-Nov-85 Cl removed procs we decided not to use
7-Nov-85 changedname from CompressAssistImpl
7-Nov-85 changed return values at end of page from NIL to lptNextPage}