{
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}