LisaList2

Advanced search  

News:

2022.06.03 added links to LisaList1 and LisaFAQ to the General Category

Pages: [1]   Go Down

Author Topic: How does the Lisa's icon-compression algorithm work?  (Read 4013 times)

AlexTheCat123

  • Sr. Member
  • ****
  • Karma: +64/-1
  • Offline Offline
  • Posts: 207
How does the Lisa's icon-compression algorithm work?
« on: April 12, 2024, 06:28:41 pm »

In the Lisa Hardware Manual, it says that expansion card icons can be stored in a compressed format if the MSB of the icon count byte is set. And it also states that "a special program is currently available to do the compression", but I'm guessing that program has probably been lost to time. Does anybody know how this compression algorithm works and how the compressed icons are stored? After compression, are all icons the same length in ROM or or does the length of the icon vary based on the efficiency of the compression on that particular icon?
Logged

sigma7

  • Administrator
  • Sr. Member
  • *****
  • Karma: +132/-1
  • Offline Offline
  • Posts: 338
  • Warning: Memory errors found. Verify comments.
Re: How does the Lisa's icon-compression algorithm work?
« Reply #1 on: April 13, 2024, 01:56:19 am »

In the Lisa Hardware Manual, it says that expansion card icons can be stored in a compressed format if the MSB of the icon count byte is set. And it also states that "a special program is currently available to do the compression", but I'm guessing that program has probably been lost to time. Does anybody know how this compression algorithm works and how the compressed icons are stored? After compression, are all icons the same length in ROM or or does the length of the icon vary based on the efficiency of the compression on that particular icon?

A snippet from Chuck Lukaszewski (author of MW+) says:

Code: [Select]
* the unpacking routine gets a byte of 8 flags */
* shifts flags right 1 bit, if the carry is set, clears a byte on the screen */
* if the carry is clear, copies the next byte to the screen */
* after doing all 128 screen bytes, the routine takes the top line */
* and XORs it with the line below it, then takes that line and XORs it */
* with the one below and so on to the bottom */

In the "Apple Lisa Boot ROM Listing.pdf" the unpack routine DSPICON is at 0x35E2

In the source file "Lisa Graphics RM248.G.TEXT" :

Code: [Select]
;---------------------------------------------------------------------
;
;  Routine to display compressed icon.
;
; INPUTS:
;       A2 = pointer to compressed icon
;       A6 = pointer to (even!) screen address for upper left hand
;      corner of icon
; SIDE EFFECTS:
;       A6 is trashed
;---------------------------------------------------------------------

DSPICON
        MOVEM.L D0-D2/A0/A2,-(SP)       ;         CHG009
        MOVE.L  A6,A0         ; save screen start address

        MOVEQ   #23,D1         ; There are 24 octals in an icon
        MOVEQ   #5,D2         ; reset row bytes counter

DLOOP   MOVE    #$100,D0         ; prime D0 for 8 bit count count
        MOVE.B  (A2)+,D0         ; load map byte from compressed image

MLOOP   LSR.W   #1,D0         ; shift off map bit
        BEQ.S   DONE         ; byte done when = 0
        BCC.S   BLACK         ; dispatch on the bit
        CLR.B   (A6)+         ; store zero in new
        BRA.S   CHECK         ; continue for all 8 bits
BLACK   MOVE.B  (A2)+,(A6)+         ; store byte in new

CHECK   DBF     D2,MLOOP         ; see if on scanline seam(every 6 bytes)
        ADDA    #90-6,A6         ; bump to next scanline         RM015
        MOVEQ   #5,D2         ; reset row bytes counter
        BRA.S   MLOOP         ; continue for all 8 bits

DONE    DBF     D1,DLOOP         ; do the rest of the octals in ICON

; Now unXOR the icon on the screen

        MOVE.L  A0,A6         ; get screen pointer saved above
        MOVE.L  A6,A2         ; second pointer
        ADDA    #90,A2         ; scanline pointer         RM015

        MOVE    #30,D1         ; do 31 scanlines

; This is the cause of the even destination restriction

XLOOP   MOVE.L  (A6)+,D0         ; get long from previous scanline
        EOR.L   D0,(A2)+         ; xor into this scanline
        MOVE.W  (A6)+,D0         ; get word from previous scanline
        EOR.W   D0,(A2)+         ; xor into this scanline
        ADDA    #90-6,A2         ; next scan line + rowbytes     RM015
        ADDA    #90-6,A6         ; next scan line + rowbytes     RM015

        DBF     D1,XLOOP

        MOVEM.L (SP)+,D0-D2/A0/A2       ;         CHG009
        RTS

The #90 constants are screen size dependent ( # horizontal pixels / 8 ) so would be different in the 3A ROM, but this doesn't affect the compression algorithm, only the code that draws into the screenbuffer.



I think the compression goes like this:

Starting with the final bitmap...

Step 1: Turn solid black blocks into zeros by using XOR to encode only the changes from row to row:

Start at the bottom (last) row, XOR with the (second last) row above it, to obtain the last row of the uncompressed data, XOR that with the (third last) row of original data to obtain the second last row of uncompressed data. Repeat until you reach the top row which is copied verbatim to the uncompressed data.

Step 2: Now the compression step will remove the zero bytes from the uncompressed data from step 1: prior to each run of 8 6 bytes in a row, a flag byte is added, where each flag bit corresponds to an image data byte in a row from step 1. If an image data byte is zero, the corresponding flag bit is set and that zero image data byte is removed (thus saving a byte).



Hence the compression effectiveness depends on the icon. If the icon is a checkerboard, the compression method actually increases the size because the flag bytes are added but there are no zero bytes to remove. If the icon is all white, all the data bytes are removed and only the flag bytes remain.

I once had a suspicion that the Macintosh used a similar icon compression method, but I don't recall if that was confirmed or not.

HTH, I apologize for my errors above, I hope they are easy to find.

edit: I now see that the code is for a 48 bit wide icon, so the rows are 6 bytes and so only 6 flag bits are used per row

edit2: it looks like the BEQ.S DONE branch in MLOOP might be to ... ummm changed my mind...
« Last Edit: April 13, 2024, 02:09:43 am by sigma7 »
Logged
Warning: Memory errors found. ECC non-functional. Verify comments if accuracy is important to you.

pablo_marx

  • Newbie
  • *
  • Karma: +2/-0
  • Offline Offline
  • Posts: 1
Re: How does the Lisa's icon-compression algorithm work?
« Reply #2 on: April 13, 2024, 04:05:35 pm »

A rough translation of the decompression routine into JavaScript:

Code: [Select]
const iconWidth = 48;
const iconHeight = 32;
const bytesPerRow = iconWidth / 8;

var framebuffer = new Array(iconHeight * bytesPerRow);
framebuffer.fill(0);

var output = 0;
for (var input=0; input<compressed.length; input+=1) {
var byte = compressed[input];
for (var bit=0; bit<8; bit+=1) {
var value = ((byte >> bit) & 1);
if (value == 0) {
framebuffer[output++] = compressed[++input];
}
else {
framebuffer[output++] = 0x00;
}
}
}


for (var y=1; y<iconHeight; y+=1) {
var above = y-1;
for (var x=0; x<bytesPerRow; x+=1) {
var dest = (y*bytesPerRow) + x;
var src = (above*bytesPerRow) + x;
framebuffer[dest] = framebuffer[dest] ^ framebuffer[src];
}
}

I've included that and some compressed icons from the rev H boot sources here: https://codepen.io/pablo_marx/pen/zYXLNrO

There'a a dropdown at the top to select the icon. That'll populate the text field with the bytes from the sources.  Alternatively if I missed some icons in the sources, one should be able to paste the bytes into the text field.  And any time the text field changes it should render the icon beneath the text field.  And finally, one should be able to right click the icon and do Save Image As if they'd like to keep it.
Logged

AlexTheCat123

  • Sr. Member
  • ****
  • Karma: +64/-1
  • Offline Offline
  • Posts: 207
Re: How does the Lisa's icon-compression algorithm work?
« Reply #3 on: April 13, 2024, 05:45:19 pm »

Wow, thanks so much guys! It makes a lot more sense now!
Logged
Pages: [1]   Go Up