root/dwt/internal/image/LZWCodec.d

/*******************************************************************************
 * Copyright (c) 2000, 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 * Port to the D programming language:
 *     Frank Benoit <benoit@tionex.de>
 *******************************************************************************/
module dwt.internal.image.LZWCodec;


import dwt.internal.image.LZWNode;
import dwt.internal.image.LEDataInputStream;
import dwt.internal.image.LEDataOutputStream;
import dwt.DWT;
import dwt.graphics.ImageData;
import dwt.graphics.ImageLoader;
import dwt.graphics.ImageLoaderEvent;
import dwt.dwthelper.utils;

import tango.core.Exception;

final class LZWCodec {
    int bitsPerPixel, blockSize, blockIndex, currentByte, bitsLeft,
        codeSize, clearCode, endCode, newCodes, topSlot, currentSlot,
        imageWidth, imageHeight, imageX, imageY, pass, line, codeMask;
    byte[] block, lineArray;
    int[] stack, suffix, prefix;
    LZWNode[] nodeStack;
    LEDataInputStream inputStream;
    LEDataOutputStream outputStream;
    ImageData image;
    ImageLoader loader;
    bool interlaced;
    static final int[] MASK_TABLE = [
        0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F,
        0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF
    ];

/**
 * Decode the input.
 */
void decode() {
    int code;
    int oc = 0;
    int fc = 0;
    byte[] buf = new byte[imageWidth];
    int stackIndex = 0;
    int bufIndex = 0;
    int c;
    while ((c = nextCode()) !is endCode) {
        if (c is clearCode) {
            codeSize = bitsPerPixel + 1;
            codeMask = MASK_TABLE[bitsPerPixel];
            currentSlot = newCodes;
            topSlot = 1 << codeSize;
            while ((c = nextCode()) is clearCode) {}
            if (c !is endCode) {
                oc = fc = c;
                buf[bufIndex] = cast(byte)c;
                bufIndex++;
                if (bufIndex is imageWidth) {
                    nextPutPixels(buf);
                    bufIndex = 0;
                }
            }
        } else {
            code = c;
            if (code >= currentSlot) {
                code = oc;
                stack[stackIndex] = fc;
                stackIndex++;
            }
            while (code >= newCodes) {
                stack[stackIndex] = suffix[code];
                stackIndex++;
                code = prefix[code];
            }
            stack[stackIndex] = code;
            stackIndex++;
            if (currentSlot < topSlot) {
                fc = code;
                suffix[currentSlot] = fc;
                prefix[currentSlot] = oc;
                currentSlot++;
                oc = c;
            }
            if (currentSlot >= topSlot) {
                if (codeSize < 12) {
                    codeMask = MASK_TABLE[codeSize];
                    codeSize++;
                    topSlot = topSlot + topSlot;
                }
            }
            while (stackIndex > 0) {
                stackIndex--;
                buf[bufIndex] = cast(byte)stack[stackIndex];
                bufIndex++;
                if (bufIndex is imageWidth) {
                    nextPutPixels(buf);
                    bufIndex = 0;
                }
            }
        }
    }
    if (bufIndex !is 0 && line < imageHeight) {
        nextPutPixels(buf);
    }
}
/**
 * Decode the LZW-encoded bytes in the given byte stream
 * into the given DeviceIndependentImage.
 */
public void decode(LEDataInputStream inputStream, ImageLoader loader, ImageData image, bool interlaced, int depth) {
    this.inputStream = inputStream;
    this.loader = loader;
    this.image = image;
    this.interlaced = interlaced;
    this.bitsPerPixel = depth;
    initializeForDecoding();
    decode();
}
/**
 * Encode the image.
 */
void encode() {
    nextPutCode(clearCode);
    int lastPrefix = encodeLoop();
    nextPutCode(lastPrefix);
    nextPutCode(endCode);

    // Write out last partial block
    if (bitsLeft is 8) {
        block[0] = cast(byte)(blockIndex - 1); // Nothing in last byte
    } else {
        block[0] = cast(byte)(blockIndex); // Last byte has data
    }
    writeBlock();

    // Write out empty block to indicate the end (if needed)
    if (block[0] !is 0) {
        block[0] = 0;
        writeBlock();
    }
}
/**
 * Encode the bytes into the given byte stream
 * from the given DeviceIndependentImage.
 */
public void encode(LEDataOutputStream byteStream, ImageData image) {
    this.outputStream = byteStream;
    this.image = image;
    initializeForEncoding();
    encode();
}
/**
 * Encoding loop broken out to allow early return.
 */
int encodeLoop() {
    int pixel = nextPixel();
    bool found;
    LZWNode node;
    while (true) {
        int currentPrefix = pixel;
        node = nodeStack[currentPrefix];
        found = true;
        pixel = nextPixel();
        if (pixel < 0)
            return currentPrefix;
        while (found && (node.children !is null)) {
            node = node.children;
            while (found && (node.suffix !is pixel)) {
                if (pixel < node.suffix) {
                    if (node.left is null) {
                        node.left = new LZWNode();
                        found = false;
                    }
                    node = node.left;
                } else {
                    if (node.right is null) {
                        node.right = new LZWNode();
                        found = false;
                    }
                    node = node.right;
                }
            }
            if (found) {
                currentPrefix = node.code;
                pixel = nextPixel();
                if (pixel < 0)
                    return currentPrefix;
            }
        }
        if (found) {
            node.children = new LZWNode();
            node = node.children;
        }
        node.children = null;
        node.left = null;
        node.right = null;
        node.code = currentSlot;
        node.prefix = currentPrefix;
        node.suffix = pixel;
        nextPutCode(currentPrefix);
        currentSlot++;
        // Off by one?
        if (currentSlot < 4096) {
            if (currentSlot > topSlot) {
                codeSize++;
                codeMask = MASK_TABLE[codeSize - 1];
                topSlot *= 2;
            }
        } else {
            nextPutCode(clearCode);
            for (int i = 0; i < nodeStack.length; i++)
                nodeStack[i].children = null;
            codeSize = bitsPerPixel + 1;
            codeMask = MASK_TABLE[codeSize - 1];
            currentSlot = newCodes;
            topSlot = 1 << codeSize;
        }
    }
}
/**
 * Initialize the receiver for decoding the given
 * byte array.
 */
void initializeForDecoding() {
    pass = 1;
    line = 0;
    codeSize = bitsPerPixel + 1;
    topSlot = 1 << codeSize;
    clearCode = 1 << bitsPerPixel;
    endCode = clearCode + 1;
    newCodes = currentSlot = endCode + 1;
    currentByte = -1;
    blockSize = bitsLeft = 0;
    blockIndex = 0;
    codeMask = MASK_TABLE[codeSize - 1];
    stack = new int[4096];
    suffix = new int[4096];
    prefix = new int[4096];
    block = new byte[256];
    imageWidth = image.width;
    imageHeight = image.height;
}
/**
 * Initialize the receiver for encoding the given
 * byte array.
 */
void initializeForEncoding() {
    interlaced = false;
    bitsPerPixel = image.depth;
    codeSize = bitsPerPixel + 1;
    topSlot = 1 << codeSize;
    clearCode = 1 << bitsPerPixel;
    endCode = clearCode + 1;
    newCodes = currentSlot = endCode + 1;
    bitsLeft = 8;
    currentByte = 0;
    blockIndex = 1;
    blockSize = 255;
    block = new byte[blockSize];
    block[0] = cast(byte)(blockSize - 1);
    nodeStack = new LZWNode[1 << bitsPerPixel];
    for (int i = 0; i < nodeStack.length; i++) {
        LZWNode node = new LZWNode();
        node.code = i + 1;
        node.prefix = -1;
        node.suffix = i + 1;
        nodeStack[i] = node;
    }
    imageWidth = image.width;
    imageHeight = image.height;
    imageY = -1;
    lineArray = new byte[imageWidth];
    imageX = imageWidth + 1; // Force a read
}
/**
 * Answer the next code from the input byte array.
 */
int nextCode() {
    int code;
    if (bitsLeft is 0) {
        if (blockIndex >= blockSize) {
            blockSize = readBlock();
            blockIndex = 0;
            if (blockSize is 0) return endCode;
        }
        blockIndex++;
        currentByte = block[blockIndex] & 0xFF;
        bitsLeft = 8;
        code = currentByte;
    } else {
        int shift = bitsLeft - 8;
        if (shift < 0)
            code = currentByte >> (0 - shift);
        else
            code = currentByte << shift;
    }
    while (codeSize > bitsLeft) {
        if (blockIndex >= blockSize) {
            blockSize = readBlock();
            blockIndex = 0;
            if (blockSize is 0) return endCode;
        }
        blockIndex++;
        currentByte = block[blockIndex] & 0xFF;
        code += currentByte << bitsLeft;
        bitsLeft += 8;
    }
    bitsLeft -= codeSize;
    return code & codeMask;
}
/**
 * Answer the next pixel to encode in the image
 */
int nextPixel() {
    imageX++;
    if (imageX > imageWidth) {
        imageY++;
        if (imageY >= imageHeight) {
            return -1;
        } else {
            nextPixels(lineArray, imageWidth);
        }
        imageX = 1;
    }
    return this.lineArray[imageX - 1] & 0xFF;
}
/**
 * Copy a row of pixel values from the image.
 */
void nextPixels(byte[] buf, int lineWidth) {
    if (image.depth is 8) {
        System.arraycopy(image.data, imageY * image.bytesPerLine, buf, 0, lineWidth);
    } else {
        image.getPixels(0, imageY, lineWidth, buf, 0);
    }
}
/**
 * Output aCode to the output stream.
 */
void nextPutCode(int aCode) {
    int codeToDo = aCode;
    int codeBitsToDo = codeSize;
    // Fill in the remainder of the current byte with the
    // *high-order* bits of the code.
    int c = codeToDo & MASK_TABLE[bitsLeft - 1];
    currentByte = currentByte | (c << (8 - bitsLeft));
    block[blockIndex] = cast(byte)currentByte;
    codeBitsToDo -= bitsLeft;
    if (codeBitsToDo < 1) {
        // The whole code fit in the first byte, so we are done.
        bitsLeft -= codeSize;
        if (bitsLeft is 0) {
            // We used the whole last byte, so get ready
            // for the next one.
            bitsLeft = 8;
            blockIndex++;
            if (blockIndex >= blockSize) {
                writeBlock();
                blockIndex = 1;
            }
            currentByte = 0;
        }
        return;
    }
    codeToDo = codeToDo >> bitsLeft;

    // Fill in any remaining whole bytes (i.e. not the last one!)
    blockIndex++;
    if (blockIndex >= blockSize) {
        writeBlock();
        blockIndex = 1;
    }
    while (codeBitsToDo >= 8) {
        currentByte = codeToDo & 0xFF;
        block[blockIndex] = cast(byte)currentByte;
        codeToDo = codeToDo >> 8;
        codeBitsToDo -= 8;
        blockIndex++;
        if (blockIndex >= blockSize) {
            writeBlock();
            blockIndex = 1;
        }
    }
    // Fill the *low-order* bits of the last byte with the remainder
    bitsLeft = 8 - codeBitsToDo;
    currentByte = codeToDo;
    block[blockIndex] = cast(byte)currentByte;
}
/**
 * Copy a row of pixel values to the image.
 */
void nextPutPixels(byte[] buf) {
    if (image.depth is 8) {
        // Slight optimization for depth = 8.
        int start = line * image.bytesPerLine;
        for (int i = 0; i < imageWidth; i++)
            image.data[start + i] = buf[i];
    } else {
        image.setPixels(0, line, imageWidth, buf, 0);
    }
    if (interlaced) {
        if (pass is 1) {
            copyRow(buf, 7);
            line += 8;
        } else if (pass is 2) {
            copyRow(buf, 3);
            line += 8;
        } else if (pass is 3) {
            copyRow(buf, 1);
            line += 4;
        } else if (pass is 4) {
            line += 2;
        } else if (pass is 5) {
            line += 0;
        }
        if (line >= imageHeight) {
            pass++;
            if (pass is 2) line = 4;
            else if (pass is 3) line = 2;
            else if (pass is 4) line = 1;
            else if (pass is 5) line = 0;
            if (pass < 5) {
                if (loader.hasListeners()) {
                    ImageData imageCopy = cast(ImageData) image.clone();
                    loader.notifyListeners(
                        new ImageLoaderEvent(loader, imageCopy, pass - 2, false));
                }
            }
        }
        if (line >= imageHeight) line = 0;
    } else {
        line++;
    }
}
/**
 * Copy duplicate rows of pixel values to the image.
 * This is to fill in rows if the image is interlaced.
 */
void copyRow(byte[] buf, int copies) {
    for (int i = 1; i <= copies; i++) {
        if (line + i < imageHeight) {
            image.setPixels(0, line + i, imageWidth, buf, 0);
        }
    }
}
/**
 * Read a block from the byte stream.
 * Return the number of bytes read.
 * Throw an exception if the block could not be read.
 */
int readBlock() {
    int size = -1;
    try {
        size = inputStream.read();
        if (size is -1) {
            DWT.error(DWT.ERROR_INVALID_IMAGE);
        }
        block[0] = cast(byte)size;
        size = inputStream.read(block, 1, size);
        if (size is -1) {
            DWT.error(DWT.ERROR_INVALID_IMAGE);
        }
    } catch (Exception e) {
        DWT.error(DWT.ERROR_IO, e);
    }
    return size;
}
/**
 * Write a block to the byte stream.
 * Throw an exception if the block could not be written.
 */
void writeBlock() {
    try {
        outputStream.write(block, 0, (block[0] & 0xFF) + 1);
    } catch (Exception e) {
        DWT.error(DWT.ERROR_IO, e);
    }
}
}