NetSurf AGA optimizing

[Thorham]

Originally Posted by PeterK

I came to the conclusion that NetSurf needs a totally different solution than my color recuction code since it creates a seperate palette for every image which is not really suitable for a browser.

Ouch, that's slow

Originally Posted by PeterK

But I've no idea yet how good the image quality could be without using any dithering (at least not in the first version based on this direct color to palette assignment method).

It'll be crappy Sierra Filter Lite is as good as Floyd Steinberg and faster. Very optimizable, too. An alternative is meynaf's HAM8 rendering method. Pretty easy to use, and about 120 cycles per pixel on a 68030. Also, it looks quite good.

[daxb]

We are talking about AGA. So image quality shouldn`t important. Speed and usefulness have highest priority. If it is possible to have more speed with less colors (128, 64, 32) it would be better.

Yes, the fastest image rendering for/on AGA I`ve seen is by meynaf (picture viewer called "V"). Unfortunately, I`ve also seen his frensh comments in his source.

[Thorham]

Originally Posted by daxb

Speed and usefulness have highest priority.

16 gray scale option, perhaps?

Originally Posted by daxb

Unfortunately, I`ve also seen his frensh comments in his source.

I know my way around the HAM8 rendering part of his source code. Really, it's no problem

[PeterK]

To get a first impression of how much image quality can be realized with a fixed 216 color palette (RGB = 6x6x6, values 15, 60, 105, 150, 195 and 240) I loaded it with FullPalette and made a screenshot of the Nature icon and the PNG image displayed by MultiView with dithering.

The expected quality of the final conversion routine which I want to write should be somewhere in the middle between both results on the screenshot. The dithering won't be as good as on the PNG image but it should look better than the colormapped icon. And of course, it will not need any color comparison at all.

In my opinion this method which maps the pixels directly to the 216 colors + 3 of the system colors should be very fast and still looking good enough for an AGA system. Tell me what you think about it before I waste my time with writing this procedure.

[Leffmann]

Here's a bit better and more complete version that uses the RGB cube palette from LibNSFB to produce a dithered image.

DitherImage(void* in24bit, void* out8bit, void* palette, int width, int height)

[PeterK]

More questions for me now than an answer

Did you write the code for that object file? Where is the source?
Which palette is that, is it fixed or dynamic? If fixed, which colors are used?

[Leffmann]

It uses and is optimized for the fixed RGB cube palette from LibNSFB. I'll clean up the source later this evening and upload it.

[NovaCoder]

Guys,

I already provided a good solution to Arti above, if the palette index lookups are cached it should result in a significant performance increase to NetSurf AGA.

After this has been implemented we can look at further improving performance by using a faster palette mapping algorithm.

The important thing to remember is that the input color to be converted to a palette index is a 32bit ABGR value. To use a different color representation value would mean a massive change to the core NetSurf code.


The only method that needs to be changed to support a palette lookup table is this one:

static uint8_t colour_to_pixel(nsfb_t *nsfb, nsfb_colour_t c)

Any further palette calculation optimizations should be done in this method:

/** Find best palette match for given colour. */
static inline uint8_t nsfb_palette_best_match(struct nsfb_palette_s *palette,
                nsfb_colour_t c, int *r_error, int *g_error, int *b_error)

[Thorham]

Originally Posted by NovaCoder

I already provided a good solution to Arti above, if the palette index lookups are cached it should result in a significant performance increase to NetSurf AGA.

Sorry to say this, but it's not a good solution You can simply use a fixed palette with a simple lookup table that's generated once. You can even store it on disk. No need for a cache, and no need for color comparisons.

Using a dynamically calculated palette for each page is of course out of the question because it becomes way to slow (not to mention that the whole page has to be rendered first, including all the images).

It all boils down to two choices:

1) Fixed palette with optional error diffusion (Sierra Filter Lite, easier to optimize, faster and just as good as Floyd Steinberg).
2) HAM8 or HAM6. Much faster than calculating a palette, looks better, and can be used for rendering pages dynamically like a fixed palette allows.

I say that if you want real speed you go for option 1 and forget everything else

[NovaCoder]

Originally Posted by Thorham

Sorry to say this, but it's not a good solution You can simply use a fixed palette with a simple lookup table that's generated once. You can even store it on disk. No need for a cache, and no need for color comparisons.

A) A fixed palette across all web pages will not look pretty
B) You will still need to convert each 32bit ABGR value to your fixed palette index

HAM mode is not really an option because the SDL it is built on doesn't support it (only 8 bit modes are supported by AGA SDL)

[Thorham]

Originally Posted by NovaCoder

A) A fixed palette across all web pages will not look pretty

No, it won't, but you don't have a choice. Generating a palette for a page that's several screens high takes too long.

Originally Posted by NovaCoder

B) You will still need to convert each 32bit ABGR value to your fixed palette index

That's what the lookup table is for

Originally Posted by NovaCoder

HAM mode is not really an option because the SDL it is built on doesn't support it (only 8 bit modes are supported by AGA SDL)

HAM8 IS an 8bit mode

Calculating a palette for every page is ridiculous if you want speed. It doesn't work from a usability perspective. Imagine a forum page that's six screens or more tall. It's going to take for ages. And for what? It's not usable.

[daxb]

IMHO go for the speed not quality. You all know with AGA you are limited and so image quality, but if someone really wants... make it optional (config switch speed|quality). Me, for example is using IBrowse with 64 colors on AGA for better use.

Edit: And if you get more speed with 16 gray scale, why not.

[Thorham]

Originally Posted by daxb

Edit: And if you get more speed with 16 gray scale, why not.

You sure do: Four bit planes=faster c2p, and converting to gray is faster than converting to lookup table values:

;
; color lookup table rrrrrggggggbbbbb (16 bits)
;
	clr.w	d0
	move.b	(a0)+,d0
	lsl.w	#5,d0
	move.b	(a0)+,d0
	lsl.w	#6,d0
	move.b	(a0)+,d0
	lsr.w	#2,d0
	move.b	(a1,d0.w),d0 ; color palette vlue
;	
; gray scale 1xRed 2xGreen 1xBlue (better and faster than plain average)
;
	clr.w	d0
	clr.w	d1
.loop
	move.b	(a0)+,d0
	move.b	(a0)+,d1
	add.w	d1,d0
	add.w	d1,d0
	move.b	(a0)+,d1
	add.w	d1,d0
	lsr.w	#6,d0 ; 4bit gray value.

Also, gray scale error diffusion is faster than color, although you can use a table for palette based error diffusion.

Gray scale would be a nice option for people who want the best speed possible. Fixed palette for people who want color while still having good speed, and HAM8 for maximum quality, while still getting usable speeds (probably ).

The fact that SDL AGA is limited to 8bit modes is NOT a problem for HAM8.

[Leffmann]

I think I was too quick judging NetSurf and its capabilities. Now that I look at its source code it seems the dithering code is written in a way so it just plugs in and works with everything, while the code I wrote just covers a special case.

I still believe it's a common usage case on NetSurf AGA, to draw an opaque unscaled 24-bit image on an 8-bit screen with dithering and the balanced palette, so I think my code can still be useful and a lot faster when you can identify this special case.

NovaCoder's suggestion to use a cache is good, but it's such a basic optimization that there has to be a reason it's not already been implemented. I'm guessing that either it doesn't look good when you truncate the color values to fit a reasonably sized cache, or that most images on the web have too many unique colors for the cache to make a big difference in the average case.

[Thorham]

To Leffmann:

Why not use a table to do the color conversion and the gray scale part? Just convert the RGB values to rrrrrggggggbbbbb (or 0000rrrrggggbbbb) and look up the corresponding values. Now you have the palette index and the approximations for the RGB values, including the grays.

[Leffmann]

Maybe I'm misunderstanding you, but this is exactly what the col_rgb and col_gray tables do. They take the red, green and blue components and give me the nearest color and the nearest gray, and the corresponding indices.

What do you think about the speed? It does about 84k pixels/sec on my 50MHz 68030, I don't know how other programs and algorithms perform.

[Thorham]

Originally Posted by Leffmann

Maybe I'm misunderstanding you

I actually forgot part of my post

What I mean is that you use one table that gives you the closest color, as shown in my previous post. This allows you to get rid of the distance calculations to see if a color or a gray is the closest match, because the colors and grays are in one table.

That, or I read your code wrong

Originally Posted by Leffmann

What do you think about the speed? It does about 84k pixels/sec on my 50MHz 68030, I don't know how other programs and algorithms perform.

The speed could be improved with the above idea, but I don't think anything beats Sierra Filter Lite as far as quality/speed goes.

[PeterK]

After playing for a while with my fixed 216 color palette and modifying it a bit I tested the code (less than 60 lines) with my library. It's really fast since it works without any color comparison or reading of tables or complex dithering and the result looks like this now compared to the original PNG image:

[Retrofan]

Dunno about the code, but the quality of the image is great

[PeterK]

Of course, the quality that you can get with such a fixed palette and without dithering is very limited, as you can see (honestly). But the code is really simple, not even optimized yet, something like this:

; A0 => 216 color image bytes
; A2 => ARGB imade data

                  MOVE.L   #$00F8F8F8,D2     ; filter for black
                  MOVE.L   #$FF030303,D3     ; filter for white
                  MOVEQ    #41,D4
                  MOVEQ    #45,D5

.nextpixel        CMP.B    #70,(A2)          ; 8 bit alpha channel
                  BCC.S    .visiblecolor
                  ADDQ.W   #4,A2
.settransparent   CLR.B    (A0)+             ; map alpha<70 to pen0
.checkifdone      CMPA.L   $38+8(SP),A2
                  BCS.S    .nextpixel
                  BRA.W    .return

.visiblecolor     MOVE.L   (A2)+,D0
                  MOVEQ    #1,D1             ; points to black
                  AND.L    D2,D0
                  BEQ.S    .colorfound
                  MOVE.L   A2,D0
                  LSR.L    #3,D0             ; every 2. longword
                  BCC.S    .checkwhitelevel
                  MOVEA.L  A2,A1
                  ADD.B    #22,-(A1)         ; push up blue level
                  BCC.S    .pushupgreenlevel
                  SCS      (A1)
.pushupgreenlevel ADDQ.B   #8,-(A1)
                  BCC.S    .pushupredlevel
                  SCS      (A1)
.pushupredlevel   ADDQ.B   #3,-(A1)
                  BCC.S    .checkwhitelevel
                  SCS      (A1)
.checkwhitelevel  SUBQ.W   #4,A2
                  MOVE.L   (A2)+,D0
                  MOVEQ    #2,D1             ; points to white
                  OR.L     D3,D0
                  SUBQ.L   #1,D0
                  BEQ.S    .colorfound
                  MOVEQ    #32,D1            ; 1. pen of cube
                  MOVE.B   -(A2),D0          ; blue component
                  SUB.B    D4,D0
                  BCS.S    .lowestgreen
.bluecomponent    ADDQ.L   #1,D1
                  SUB.B    D5,D0
                  BCC.S    .bluecomponent
.lowestgreen      MOVE.B   -(A2),D0          ; green component
                  SUB.B    D5,D0
                  BCS.S    .lowestred
.greencomponent   ADDQ.L   #6,D1
                  SUB.B    D5,D0
                  BCC.S    .greencomponent
.lowestred        MOVE.B   -(A2),D0
                  SUB.B    D5,D0
                  BCS.S    .cubefinished
.redcomponent     ADD.B    #36,D1
                  SUB.B    D5,D0
                  BCC.S    .redcomponent
.cubefinished     ADDQ.W   #3,A2
.colorfound       MOVE.B   D1,(A0)+          ; pixel -> register
                  BRA.S    .checkifdone