Compresses arrays of a few repeating random values using a variation on Palette Mapping.

PaletteArray.java

/*
 * I release this code into the public domain.
 */

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.zip.Deflater;

/**
 *
 * @author Jocopa3
 */
public class PaletteArray {

    
    /*
     * Reads a palette mapped array of bytes
    */
    public static int[] read(byte[] bytes) {
        ByteBuffer buffer = ByteBuffer.wrap(bytes);

        // Grab the first byte which says how many palette ID's there are
        int size = buffer.getInt();
        int[] palette = new int[size];

        // Iterate through the palette map and store each palette ID in the proper index
        int tmp;
        for (tmp = 0; tmp < size; tmp++) {
            palette[tmp] = buffer.getInt();
        }

        // bitStride = how many bits are used to store each number
        int bitStride = bitWidth(size - 1);
        int bitMask = (1 << bitStride) - 1;

        int bitPos = 0, bytePos, pair;
        int offset = buffer.position();
        int bitLength = buffer.remaining() * Byte.SIZE;
        int bitLengthA;

        int[] arr = new int[bitLength / bitStride];
        
        // Handle the case of only 1 object stored
        // There is a more efficient way to store an array of 1 object, but I'm lazy
        if (size == 1) {
            Arrays.fill(arr, palette[0]);
            return arr;
        }

        // Calculate how many values fit in the last byte
        switch (bitStride) {
            case 3:
                bitLengthA = bitLength - 9;
                break;
            case 1:
            case 2:
            case 4:
                bitLengthA = bitLength - 8;
                break;
            case 5:
            case 6:
            case 7:
            case 8:
                bitLengthA = bitLength - bitStride;
                break;
            default:
                bitLengthA = bitLength;
        }

        // Iterate until the last byte
        while (bitPos < bitLengthA) {
            bytePos = (bitPos / 8) + offset;

            // Assemble the two bytes that potentially store the palette index
            pair = (bytes[bytePos]) & 0xff;
            pair |= (bytes[bytePos + 1] & 0xff) << 8;

            // Shift and mask the pair to get the palette index
            tmp = pair >> (bitPos & 7);
            tmp &= bitMask;

            arr[bitPos / bitStride] = palette[tmp];
            
            bitPos += bitStride;
        }

        // Handle the last byte
        while (bitPos < bitLength) {
            bytePos = (bitPos >> 3) + offset;
            pair = (bytes[bytePos]) & 0xff;

            tmp = pair >> (bitPos & 7);
            tmp &= bitMask;

            arr[bitPos / bitStride] = palette[tmp];
            
            bitPos += bitStride;
        }

        return arr;
    }
    
    public static byte[] write(int uniqueIds, int[] ids) {
        // bitStride = the max amount of bits needed to store all Id's
        int bitStride = bitWidth(uniqueIds);
        int byteSize = (bitStride * ids.length)  / 8;

        // paletteMap keeps track of unique Id's
        HashMap<Integer, Integer> paletteMap = new HashMap<Integer, Integer>();
        
        byte[] bytes = new byte[(uniqueIds + 1) * Integer.BYTES + byteSize];
        ByteBuffer buffer = ByteBuffer.wrap(bytes);
        buffer.putInt(uniqueIds);

        int paletteId;
        int arrSize = ids.length;
        int offset = (uniqueIds + 1) * Integer.BYTES;
        int bitLength = arrSize * bitStride;
        int bitLengthA = bitLength - 16;

        int bit = 0, bytePos, pair;
        int id = 0;
        int i;
        
        // Iterate through all values storing each in the byte array
        for (i = 0; bit < bitLength; bit += bitStride, i++) {
            bytePos = (bit / 8) + offset;

            // Test if the value already has a palette ID
            if (!paletteMap.containsKey(ids[i])) {
                paletteMap.put(ids[i], id);
                paletteId = id;
                id++;
            } else {
                paletteId = paletteMap.get(ids[i]);
            }

            // Fit the palette ID into two bytes
            pair = bytes[bytePos] & 0xff;
            pair |= paletteId << (bit & 7);

            // Store the first byte which may hold the ID
            bytes[bytePos] = (byte) (pair & 0xff);
            
            // Store the next two bytes that may hold the ID if not at the end of the array
            if (bytePos < bytes.length - 1) {
                bytes[bytePos + 1] = (byte) ((pair >> 8) & 0xff);
            }
            if (bytePos < bytes.length - 2) {
                bytes[bytePos + 2] = (byte) ((pair >> 16) & 0xff);
            }
        }

        // Write the palette map in the header
        for (Integer f : paletteMap.keySet()) {
            buffer.position((paletteMap.get(f) + 1) * Integer.BYTES);
            buffer.putInt(f);
        }

        return bytes;
    }

    // Helper function: returns the next highest power of 2
    public static int getNextPow2(int v) {
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v++;

        return v;
    }

    // Helper function: returns the number of bits a number occupies
    public static int bitWidth(int num) {
        int bitpos;

        // Continue right-shifting one bit at a time until the number reaches 0
        for (bitpos = 0; num != 0; bitpos++) {
            num >>= 1;
        }

        // Return how many right-shifts it took to for the number to reach 0
        return bitpos;
    }

    // Compress a byte array using Java's ZIP library
    public static byte[] compress(byte[] data) throws IOException {
        Deflater deflater = new Deflater();
        deflater.setInput(data);
        
        ByteArrayOutputStream outputStream = new ByteArrayOutputStream(data.length);
        deflater.finish();
        
        byte[] buffer = new byte[1024];
        
        while (!deflater.finished()) {
            int count = deflater.deflate(buffer);   
            outputStream.write(buffer, 0, count);
        }
        
        outputStream.close();
        
        byte[] output = outputStream.toByteArray();
        
        System.out.println("Original: " + data.length);
        System.out.println("Compressed: " + output.length);
        
        return output;
    }

    // Converts an int array to a byte array
    public static byte[] intToByteArr(int[] data) {
        ByteBuffer buffer = ByteBuffer.allocate(data.length * Integer.BYTES);
        for (Integer i : data) {
            buffer.putInt(i);
        }
        
        return buffer.array();
    }

    public static void main(String[] args) throws IOException {
        // Used to track the number of unique values
        HashMap<Integer, Integer> idMap = new HashMap<Integer, Integer>();

        // Generate an array of values
        int[] ids = new int[4096];
        for (int i = 0; i < ids.length; i++) {
            
            ids[i] = (int)(Math.random() * 31); // Change this to test different scenarios
            idMap.put(ids[i], i);
        }

        // Get the number of unique values
        int uniqueIds = idMap.keySet().size();

        System.out.println("UniqueIds: " + uniqueIds + "\n");

        byte[] out = write(uniqueIds, ids);

        System.out.println("Naive Method: ");
        compress(intToByteArr(ids));
        System.out.println();
        System.out.println("Palette Method: ");
        compress(out);
        
        //read(out);
    }
}