{******************************************************}
{***************** FLOYD ALGORITHM *****************}
{******************************************************}
{ File: Floyd.mc
Create by: Martin J. Shramo, June 1986
Last Edited: 21-Apr-87 16:53:00
}
{ to list use: print gacha8/f /-a Floyd.mc }
{
ALGORITHM DESCRIPTION
The Floyd algorithm is an error distribution algorithm that converts a gray scale image into a bit map image. This is accomplished by approximating a gray scale pixel value with a single bit value. There is an error created by this approximation. If the bit value is zero, the error is the difference between the original gray scale pixel value and zero. If the bit value is one, the error is the difference between the original gray scale pixel value and maxValue. The error from this approximation is distributed to the surrounding pixels as indicated here.
[PIX] [uFWDError]
[uLFTError] [uMIDError] [uRTError]
PIX: original gray scale pixel value
uRTError: 1/16 of Error
uMIDError: 5/16 of Error
uLFTError: 3/16 of Error
uFWDError: 7/16 of Error
This instruction will operate on one line of gray scale pixels at a time. Pointers to an error buffer, the input gray scale pixels and an output bit map will be passed to this instruction. Other parameters are the number of pixels that will be processed, the threshold cut off value for approximating gray scale data with a single pixel value, and an invert flag. This invert flag causes the output to be inverted or not inverted.
}
@FLOYD:
{ Save system R and RH registers }
ULsave ← L,pCall2,CALL[fSaveRegs] ,c1,at[0,10,ESCAn];
{ fSaveRegs ,c2-c1; }
{ Determine if this is initial entry or entry after handling an interrupt/fault. A dispatch is made on the low four bits of the inverted stack value. On initial entry (or after taking a page fault when accessing the first item in the paramter block), the stack pointer should point to U2 which means the stack will have a 2 in it. If entry after handling a page fault or handling an interrupt, the stack pointer should have an E in it.}
Xbus ← ErrnIBnStkp, XDisp ,c2,at[0,10,fSaveRegsRet];
rVirtualL ← uArgVL,pop,BRANCH[fGetState,fNormalEntry,07] ,c3; { branch on high bit of ~stackP }
{ ***** fGetState PULLS DATA FROM THE STACK, RETURNS BELOW ***** }
{ Here is the case where we are returning from an interrupt or a page fault and the state of this instruction is on the stack. We need to get the appropriate parameters from the stack and into U and R registers. We also need to verify that all needed pages are in real memory.}
{ ***** PULL ALL PAGES INTO REAL MEMORY ***** }
fGetStateRet:
pCall2 ,c1;
CALL[fGetAllPages] ,c2,at[0,10];
{ ***** DETERMINE IF PAGE FAULT OR INTERRUPT ***** }
Xbus ← uSTKMisc, XDisp ,c3,at[0,10,fGetAllPagesRet];
rThisCell ← ThisCellInitVal,BRANCH[PFReturn,$,0B] ,c1;
{ interrupt return }
Xbus ← uByte,XDisp,GOTO[IntrptRtn] ,c2;
{ ***** NORMAL ENTRY ***** }
{ The Floyd instruction begins here for normal entry or entry after a page fault when accessing the first item in the paramter list. There is no difference between these two cases. Go and get the parameters from the parameter block and put them into the appropriate U registers.}
fNormalEntry:
{ check for 16 word boundry on ArgPtr }
[] ← rVirtualL and ArgBoundry,ZeroBr,L0 ← L0.Floyd ,c1;{return for MapSrc}
pop,BRANCH[FloydBadOffset,$] ,c2;
{ get real address of argument block }
rhVirtualH ← uArgVH,CALL[MapSrc] ,c3;
uMIDError ← 0 ,c3,MapSrcRet[L0.Floyd];
{ start pulling the argument list out of real memory }
MAR ← [rhSrcReal,rSrcReal + 2],pCall2 ,c1;
uRTError ← 0, CANCELBR[fRdMem,2],pRet2 ,c2,at[0,10]; { right error starts at 0 }
fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;{ input buffer low virt addr }
MAR ← [rhSrcReal,rSrcReal + 3],pCall2 ,c1,at[0,10,fRdMemRet];
uInPtrVL ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[1,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ input buffer high virt addr }
MAR ← [rhSrcReal,rSrcReal + 4],pCall2 ,c1,at[1,10,fRdMemRet];
uInPtrVH ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[2,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ input buffer byte offset }
MAR ← [rhSrcReal,rSrcReal + 5],pCall2 ,c1,at[2,10,fRdMemRet];
uByte ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[3,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ output buffer low virt addr }
MAR ← [rhSrcReal,rSrcReal + 6],pCall2 ,c1,at[3,10,fRdMemRet];
uOutPtrVL ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[4,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ output buffer high virt addr }
MAR ← [rhSrcReal,rSrcReal + 7],pCall2 ,c1,at[4,10,fRdMemRet];
uOutPtrVH ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[5,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ output buffer bit offset }
MAR ← [rhSrcReal,rSrcReal + 8],pCall2 ,c1,at[5,10,fRdMemRet];
uBit ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[6,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ error buffer low virt addr }
MAR ← [rhSrcReal,rSrcReal + 9],pCall2 ,c1,at[6,10,fRdMemRet];
uErrorPtrVL ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[7,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ error buffer high virt addr }
MAR ← [rhSrcReal,rSrcReal + 1],pCall2 ,c1,at[7,10,fRdMemRet];
uErrorPtrVH ← rTT,CANCELBR[fRdMem,2],pRet2 ,c2,at[8,10];
{fRdMem:rTT ← MD, DISP4[fRdMemRet] ,c3;}{ threshold }
MAR ← [rhSrcReal,rSrcReal + 0] ,c1,at[8,10,fRdMemRet];
uThreshAndMax ← rTT, CANCELBR[$,2] ,c2;
rTT2 ← MD ,c3; { pixel count and invert bit }
{ want to do all of the adjustments on the parameters }
uFWDError ← 0 ,c1; { forward error starts at 0 }
Q ← rTT and 0FF, ,c2;
uMaxValue ← Q ,c3;
rTT ← rTT LRot8, ,c1;
rTT ← rTT and 0FF, ,c2;
uThreshold ← rTT ,c3;
rTT2 ← RShift1 (rTT2 + rTT2), SE ← 0, CarryBr ,c1; { test and clear invert bit }
uCount ← rTT2,BRANCH[$,InvertOn,0E] ,c2;
{ Invert Bit zero }
rTT2 ← 0,GOTO[SetInvertDone] ,c3;
InvertOn:
rTT2 ← 1 ,c3;
SetInvertDone:
uPolarity ← rTT2,pCall2 ,c1;
uRtnReason ← PFRtn,CALL[fGetAllPages] ,c2,at[1,10];{ pull all pages into real memory}
Noop ,c3,at[1,10,fGetAllPagesRet];
Noop ,c1;
{ ***** ENTRY AFTER HANDLING A PAGE FAULT WHEN INITIALLY PULLING ALL PAGES INTO REAL MEMORY ***** }
PFReturn:
{ ***** INITIAL CASE WHERE NOT WRITING DATA ON WORD BOUNDARY ***** }
{ We now have to check if the output data begins at bit zero of an output word, if so then we don't have to do any special processing. If that is not the case, then we have to read in the output data word and prepare for this partial word writing.}
rTT ← uBit,ZeroBr ,c2;
rThisCell ← ThisCellInitVal,BRANCH[StartBitNot0,$] ,c3;
{ start bit zero }
MAR ← [rhSrcHi,rSrcLow + 0],GOTO[ReadSrc1] ,c1;
StartBitNot0:
MAR ← [rhDstHi,rDstLow+0] ,c1;
uBit ← 0 ,c2;{uBit←0 always where return from interrupt}
rThisCell ← MD ,c3;
rThisCell ← rThisCell RShift1,SE ← 1 ,c1;
MoreSHFT:
rTT ← rTT + 1,NibCarryBr ,c2;
BRANCH[$,ReadSrc] ,c3;
rThisCell ← rThisCell RShift1,SE ← 0,GOTO[MoreSHFT] ,c1;
{ ***** READ THE SOURCE DATA, GET A PAIR OF PIXELS ***** }
ReadSrc:
MAR ← [rhSrcHi,rSrcLow + 0] ,c1;
ReadSrc1:
rTT ← uByte,CANCELBR[$,0] ,c2;
PIX ← MD ,c3;
uSaveINWrd ← PIX ,c1;
rTT ← rTT xor 1, ZeroBr ,c2;
uByte ← rTT, BRANCH[$,RTByte] ,c3;
{ want left byte from pixel pair }
rTT2 ← PIX and ~(0FF) ,c1;
rTT ← rTT2 LRot8,GOTO[GotPixel] ,c2;
{ want right byte from pixel pair }
RTByte:
Noop ,c1;
rTT ← PIX and 0FF ,c2;
{ ***** ADJUST CURRENT PIXEL VALUE ***** }
GotPixel: {rTT has current pixel }
PIX ← uFWDError ,c3;
{ Get error buffer value }
MAR ← [rhErrHi,rErrLow + 0] ,c1;
PIX ← PIX + rTT,CANCELBR[$,0] ,c2; { PIX adjusted pixel value }
rTT ← MD ,c3;
{ do final adjustment on PIX and generate new error value }
PIX ← rTT + PIX ,c1;
rTT2 ← uThreshold ,c2;
{ ***** DETERMINE DESTINATION BIT, GET NEW ERROR VALUE ***** }
Q ← rTT2 - PIX - 1,NegBr ,c3; { sign of Q ← output bit }
rTT ← uMaxValue,BRANCH[OffBit,$] ,c1;
{ bit value is on, new error is (pixel - MaxPixel) }
rError ← PIX - rTT, NegBr, GOTO[PartialError] ,c2;
{ bit value is off, new error is (pixel - 0) }
OffBit: rError ← PIX, NegBr ,c2;
PartialError:
rTT4 ← uMIDError, BRANCH[PosPartialError,NegPartialError] ,c3;
{ we now have to generate negative partial error values }
NegPartialError:
rTT ← -rError ,c1;
rTT ← rTT RShift1,SE ← 0 ,c2;
rTT ← rTT RShift1,SE ← 0 ,c3; { rTT ← -error/4 }
rTT3 ← rTT RShift1,SE ← 0 ,c1; { rTT3 ← -error/8 }
rTT2 ← rTT3 RShift1,SE ← 0 ,c2; { rTT2 ← -error/16 }
rTT2 ← -rTT2 ,c3; { rTT2 ← error/16 }
rTT3 ← rTT2 - rTT3 ,c1; { rTT3 ← error*3/16 }
rTT ← rTT2 - rTT ,c2; { rTT ← error*5/16 }
GOTO[GotBit] ,c3;
{ we now have to generate positive partial error values }
PosPartialError:
rTT ← rError RShift1,SE ← 0 ,c1;
rTT ← rTT RShift1,SE ← 0 ,c2; { rTT ← error/4 }
rTT3 ← rTT RShift1,SE ← 0 ,c3; { rTT3 ← error/8 }
rTT2 ← rTT3 RShift1,SE ← 0 ,c1; { rTT2 ← error/16}
rTT3 ← rTT3 + rTT2 ,c2; { rTT3 ← error*3/16 }
rTT ← rTT + rTT2 ,c3; { rTT ← error*5/16 }
{ ***** DISTRIBUTE ERROR, UPDATE ERROR BUFFER ***** }
{ update the error buffer value }
GotBit:
MAR ← [rhOldErrorHi,rOldErrorLow + 0] ,c1;
MDR ← rTT4 + rTT3 ,c2;
{ update Middle error }
rTT4 ← uRTError ,c3;
rTT4 ← rTT4 + rTT ,c1;
uMIDError ← rTT4 ,c2;
{ update Right error }
uRTError ← rTT2, rError ← rError - rTT2 ,c3;
{ update Forward error }
rError ← rError - rTT3 ,c1;
rError ← rError - rTT ,c2;
uFWDError ← rError ,c3; { propagate remaining error forward }
{ shift in a bit for the current pixel }
rThisCell ← DLShift1 rThisCell,NegBr ,c1;
rThisCell ← rThisCell xor uPolarity,pCall2,BRANCH[CellNotFull,$] ,c2;
{ the cell IS FULL, set L2 to 1 }
rTT2 ← uCount,GOTO[TestForDone] ,c3,at[1,10];
CellNotFull:
{ the cell IS NOT FULL, set L2 to 0 }
rTT2 ← uCount ,c3,at[0,10];
{ ***** TEST TO SEE IF ALL PIXELS ARE PROCESSED ***** }
{ we have now processed another input pixel, see if we are done }
TestForDone:
rTT2 ← rTT2 - 1,ZeroBr ,c1;
uCount ← rTT2,L2Disp,BRANCH[$,NoMorePixels] ,c2;
{ there is more to do, check for full rThisCell }
rOldErrorLow ← rErrLow,BRANCH[AdjRealErrPtr,$] ,c3;
{ ***** WRITE OUT OUTPUT BUFFER ***** }
{ we have to write out rThisCell }
WriteThisCell:
MAR ← [rhDstHi,rDstLow + 0] ,c1;
MDR ← rThisCell,rTT3 ← 0FF + 1 ,c2;
rThisCell ← ThisCellInitVal ,c3;
{ ***** UPDATE THE DESTINATION ADDRESSES ***** }
{ update the real destination address }
AdjRealDstPtr:
rDstLow ← rDstLow + 1,PgCarryBr ,c1;
rVirtualL ← uOutPtrVL,BRANCH[NoDstCarry,$] ,c2;
{there is a real page cross, update the virtual destination address }
rVirtualL ← rVirtualL and ~(0FF),L0 ← L0.FloydLoop ,c3;{return for MapDst}
rVirtualL ← rVirtualL + rTT3,CarryBr ,c1;
uOutPtrVL ← rVirtualL,BRANCH[NoTopCarry,$] ,c2;
{ need to carry to rh register }
Q ← uOutPtrVH ,c3;
Q ← Q + 1 ,c1;
uOutPtrVH ← Q ,c2;
{ at this point the U and R registers have been updated, now remap }
NoTopCarry:
rhVirtualH ← uOutPtrVH,CALL[MapDst] ,c3;
rDstLow ← rDstReal ,c3,MapDstRet[L0.FloydLoop];{can't have a page fault}
Q ← rhDstReal ,c1;
rhDstHi ← Q LRot0 ,c2;
{ ***** UPDATE THE ERROR BUFFER ADDRESSES ***** }
{need to update the error buffer addresses }
NoDstCarry:
Noop ,c3;
AdjRealErrPtr:
Q ← rhErrHi ,c1;{update the error address to write to}
rhOldErrorHi ← Q LRot0 ,c2;{ rOldErrorLow updated at BitSetUp }
rErrLow ← rErrLow + 1, PgCarryBr ,c3;
rVirtualL ← uErrorPtrVL,BRANCH[NoErrCarry,$] ,c1;
{ there is a real page cross, update the virtual address }
rTT3 ← 0FF + 1,L0 ← L0.FloydLoopErrBuf ,c2;{return for MapDst}
rVirtualL ← rVirtualL and ~(0FF) ,c3;
rVirtualL ← rVirtualL + rTT3,CarryBr ,c1;
uErrorPtrVL ← rVirtualL,BRANCH[NoErrTopCarry,$] ,c2;
{ need to carry to rh register }
Q ← uErrorPtrVH ,c3;
Q ← Q + 1 ,c1;
uErrorPtrVH ← Q ,c2;
{ at this point the U and R registers have been updated now remap }
NoErrTopCarry:
rhVirtualH ← uErrorPtrVH,CALL[MapDst] ,c3;
rErrLow ← rDstReal ,c3,MapDstRet[L0.FloydLoopErrBuf]; {can't have page faults}
Q ← rhErrHi ,c1;{update the address to write to (rh)}
rhOldErrorHi ← Q LRot0 ,c2;
Q ← rhDstReal ,c3;
rhErrHi ← Q LRot0 ,c1;
{ ***** CHECK FOR INTERRUPTS PENDING ***** }
NoErrCarry:
{ checking for pending interrupts }
rTT ← INTRtn,MesaIntBr,pCall0 ,c2;
[] ← rThisCell - 1,NZeroBr,BRANCH[NoIntPend,$] ,c3,at[1,10];
{interrupt pending, handle only at dest word boundary}
uRtnReason ← rTT,BRANCH[fSaveState,NoCheckInt] ,c1;
{ need to save the state of the instruction }
{ fSaveState ,c2-c3; }
{ fRestoreRegs ,c1-c1; }
stackP ← 0E ,c2,at[1,10,fRestoreRegsRet];
TOS ← uSTKMisc,GOTO[Bank1Interrupt] ,c3;
NoIntPend:
CANCELBR[$,1] ,c1;
{ ***** GET ANOTHER SOURCE PIXEL TO PROCESS ***** }
NoCheckInt:
{ we still have more pixels to process, get pixels from input }
Xbus ← uByte,XDisp ,c2;
{ ***** INTERRUPT RETURN AFTER GETTING STATE AND PULLING PAGES IN REAL MEMORY ***** }
IntrptRtn:
uByte ← 0,BRANCH[NoPixel,GetRTByte,0E] ,c3; {uByte toggled for GetRTByte}
{ need to update input pointer and get another pixel pair }
NoPixel:
rSrcLow ← rSrcLow + 1, PgCarryBr ,c1;
rVirtualL ← uInPtrVL,BRANCH[NoInCarry,$] ,c2;
{ there is a real page cross, update the source virtual address }
rTT3 ← 0FF + 1,L0 ← L0.FloydLoop ,c3;{return for MapSrc}
rVirtualL ← rVirtualL and ~(0FF) ,c1;
rVirtualL ← rVirtualL + rTT3,CarryBr ,c2;
uInPtrVL ← rVirtualL,BRANCH[NoInTopCarry,$] ,c3;
{ need to carry to rh register }
Q ← uInPtrVH ,c1;
Q ← Q + 1 ,c2;
uInPtrVH ← Q ,c3;
{ at this point the U and R registers have been updated, now remap }
NoInTopCarry:
Noop ,c1;
Noop ,c2;
rhVirtualH ← uInPtrVH,CALL[MapSrc] ,c3;
rSrcLow ← rSrcReal ,c3,MapSrcRet[L0.FloydLoop];{can't have page faults}
Q ← rhSrcReal ,c1;
rhSrcHi ← Q LRot0 ,c2;
NoInCarry:
uByte ← 0,GOTO[ReadSrc] ,c3; {want to start with left pixel of pair}
GetRTByte:
PIX ← uSaveINWrd ,c1;
rTT ← PIX and 0FF,GOTO[GotPixel] ,c2;
{ ***** END WHERE LAST MIDDLE ERROR NEEDS TO BE WRITTEN TO ERROR BUFFER ***** }
{ note, rErrLow and rhErrHi have not been updated for the next pixel to process, hence, the location to write uMIDError is the current rErrLow and rhErrHi }
NoMorePixels:
rTT3 ← uMIDError,CANCELBR[$,1] ,c3;
MAR ← [rhErrHi,rErrLow + 0] ,c1;
MDR ← rTT3 ,c2;
{ ***** DETERMINE IF WE HAVE A FULL OR PARTIAL WORD TO WRITE ***** }
L2Disp ,c3;{0 means not full, 1 means full rThisCell}
MAR ← [rhDstHi,rDstLow + 0],BRANCH[EndIsNotFull,$] ,c1;
MDR ← rThisCell,pCall0,GOTO[FloydNormalReturn] ,c2;
{ ***** END CASE WHERE NOT WRITING FULL DESTINATION WORD ***** }
EndIsNotFull:
rTT ← 0 ,c2;
rTT2 ← MD ,c3;
{ shift and generate masks for Dest data and new data }
MoreDstShift:
rThisCell ← rThisCell LShift1,SE ← 0,NegBr ,c1;
rTT ← rTT LShift1, SE ← 1,BRANCH[$,DstShiftDone] ,c2;
GOTO[MoreDstShift], ,c3;
{ mask out the old dest data }
DstShiftDone:
rTT ← rTT and rTT2 ,c3;
{ write out the "combined" data }
MAR ← [rhDstHi,rDstLow + 0] ,c1;
MDR ← rThisCell or rTT,pCall0 ,c2;
{ ***** NORMAL RETURN POINT *****}
FloydNormalReturn:
CALL[fRestoreRegs] ,c3,at[0,10];
{ fRestoreRegs ,c1-c1; }
stackP ← 0 ,c2,at[0,10,fRestoreRegsRet];
{ If the parameter block has an incorrect offset, we return here without processing any data. }
FloydBadOffset:
GOTO[Bank1NxtInstc1] ,c3;
{ ***** PAGE FAULT RETURN WHEN PULLING ALL PAGES INTO REAL MEMORY *****}
fSrcFlt:
uFaultParm0 ← VD,pCall0,GOTO[fComMapFlt] ,c3;
fDstFlt:
uFaultParm0 ← VD,pCall0,GOTO[fComMapFlt] ,c3;
fErrFlt:
uFaultParm0 ← VD,pCall0 ,c3;
fComMapFlt:
T ← Q,CALL[fSaveState] ,c1,at[0,10];{Q has fault type}
Q ← rhVD ,c1,at[0,10,fSaveStateRet];
uFaultParm1 ← Q,pCall0 ,c2;
stackP ← 0E,CALL[fRestoreRegs] ,c3,at[2,10];
{ fRestoreRegs ,c1-c1; }
TOS ← uSTKMisc,GOTO[Bank1Fault] ,c2,at[2,10,fRestoreRegsRet];
{ ***** PAGE FAULT RETURN WHEN PULLING IN THE ARGUMENT LIST *****}
stackP ← 2,CALL[fRestoreRegs] ,c3,MapSrcF[L0.Floyd];
{ fRestoreRegs ,c1-c1; }
GOTO[Bank1Fault] ,c2,at[L0.Floyd,10,fRestoreRegsRet];
{ ***** END *****}