Re: MMX speedup for Floyd Steinberg error diffusion


"rep_movsd" wrote in message
Hi

I recently implemented an animated GIF encoder to convert any video
into a GIF ( I know it doesnt seem really useful, but thats what the
client wanted ).

I implemented floyd steinberg error diffusion to improve quality of
the quantized output.

The code is in Visual C++ and I use 32 bpp pixels for ease in
processing.

The diffusion process takes up about 1/2 the time required to encode a
frame and it seems to be the right place to optimize.

Heres how the algorithm works - pseudocode

for each pixel in the image
{
palColor = Get color in palette thats nearest to current pixel
get signed difference between actual color and palette color for
R G and B components
add difference (with unsigned saturation) to surrounding pixels
with a weightage :
EAST -> 7/16
SOUTHWEST -> 5/16
SOUTH -> 3/16
SOUTHEAST -> 1/16
}


Now I thought I may be able to do this fast with MMX , subtracting the
3 r, g, b bytes at once ( I use 32 bpp pixels, but alpha channel is
ignored )

I can do a packed subtract to get the differences, but thereafter the
multiplication and shifting(for division by 16) seem to be impossible.

Moreover, how can one do a unsigned saturated addition of signed
difference values to the unsigned pixel values?

Any ideas anyone?


The 4 32-bit words can be stored in a single 128-bit xmm register.
Then you copy and shift left and add/subtract, because
7 = 8 - 1 = 2^3 - 1 and 5 = 4 + 1 = 2^2 + 1 etc.
Then you shift right because 16 = 2^4.
The shift is the PSLLD/PSRLD and the add/subtract is the PADDD/PSUBD.
The reference for these instructions are in:
http://developer.intel.com/products/processor/manuals/index.htm
see instruction set reference.
The timings can be found in:
http://agner.org/optimize/
Maarten.



.

Relevant Pages

  • MMX speedup for Floyd Steinberg error diffusion
    ... I recently implemented an animated GIF encoder to convert any video ... into a GIF (I know it doesnt seem really useful, but thats what the ... add difference (with unsigned saturation) to surrounding pixels ...
    (comp.lang.asm.x86)
  • color shift of desktop
    ... the red portion of the desktop pixels more and more red. ... If I move an open window it will be redrawn and the red ... shift gets lost on this part of the screen. ... The window thread draws some text into the window and ...
    (microsoft.public.win32.programmer.gdi)
  • Re: Image Shifting
    ... i want to compare 2 images in matlab....all i want to do is to ... Can you be more specific as to what you mean by "shift the pixels"? ... mean of all these white pixels ...
    (comp.soft-sys.matlab)
  • Re: Shifting an image by constant value?
    ... Or a shift in the x and y say 20 pixels in the X direction and 30 in the Y direction. ... image matrix you want to assign into, keeping in mind that images are ...
    (comp.soft-sys.matlab)
  • Re: Shifting an image by constant value?
    ... Did I misinterpret you? ... Or a shift in the x and y say 20 pixels in the X direction and 30 in the Y direction. ... image matrix you want to assign into, keeping in mind that images are ...
    (comp.soft-sys.matlab)