CraftChunkSection.java

package org.bukkit.craftbukkit;

import net.minecraft.server.Block;
import net.minecraft.server.ChunkSection;
import net.minecraft.server.NibbleArray;

import org.bukkit.craftbukkit.util.Palette;

public class CraftChunkSection extends ChunkSection {
    private int yPos;
    private int nonEmptyBlockCount;
    private int tickingBlockCount;
    private final Palette storage = new Palette();

    public CraftChunkSection(int yPos, boolean flag) {
        this.yPos = yPos;
    }

    public CraftChunkSection(int yPos, boolean flag, byte[] blkIds, byte[] extBlkIds) {
        this.yPos = yPos;

        if (extBlkIds != null) {
            NibbleArray extBlockIds = new NibbleArray(extBlkIds, 4);
            for (int x = 0; x < 16; x++) {
                for (int y = 0; y < 16; y++) {
                    for (int z = 0; z < 16; z++) {
                        int id = extBlockIds.a(x, y, z) << 8 | blkIds[y << 8 | z << 4 | x];
                        storage.setBlockTypeId(x, y, z, (short) (id & 0xFFF));
                    }
                }
            }
        } else {
            for (int x = 0; x < 16; x++) {
                for (int y = 0; y < 16; y++) {
                    for (int z = 0; z < 16; z++) {
                        storage.setBlockTypeId(x, y, z, (short) (blkIds[y << 8 | z << 4 | x] & 0xFFF));
                    }
                }
            }
        }

        recalcBlockCounts();
    }

    public int a(int x, int y, int z) {
        return storage.getBlockTypeId(x, y, z);
    }

    public void a(int x, int y, int z, int id) {
        int old_id = storage.getBlockTypeId(x, y, z);

        if (old_id == 0 && id != 0) {
            ++nonEmptyBlockCount;
            if (Block.byId[id] != null && Block.byId[id].isTicking()) {
                ++tickingBlockCount;
            }
        } else if (old_id != 0 && id == 0) {
            --nonEmptyBlockCount;
            if (Block.byId[old_id] != null && Block.byId[old_id].isTicking()) {
                --tickingBlockCount;
            }
        } else if (Block.byId[old_id] != null && Block.byId[old_id].isTicking() && (Block.byId[id] == null || !Block.byId[id].isTicking())) {
            --tickingBlockCount;
        } else if ((Block.byId[old_id] == null || !Block.byId[old_id].isTicking()) && Block.byId[id] != null && Block.byId[id].isTicking()) {
            ++tickingBlockCount;
        }

        storage.setBlockTypeId(x, y, z, (short) (id & 0xFFF));
    }

    public int b(int x, int y, int z) {
        return storage.getBlockData(x, y, z);
    }

    public void b(int x, int y, int z, int data) {
        storage.setBlockData(x, y, z, (byte) data);
    }

    public boolean a() {
        return nonEmptyBlockCount == 0;
    }

    public boolean b() {
        return tickingBlockCount > 0;
    }

    public int d() {
        return yPos;
    }

    public void c(int x, int y, int z, int skyLight) {
        storage.setBlockSkyLight(x, y, z, (byte) skyLight);
    }

    public int c(int x, int y, int z) {
        return storage.getBlockSkyLight(x, y, z);
    }

    public void d(int x, int y, int z, int emittedLight) {
        storage.setBlockEmittedLight(x, y, z, (byte) emittedLight);
    }

    public int d(int x, int y, int z) {
        return storage.getBlockEmittedLight(x, y, z);
    }

    public void recalcBlockCounts() {
        nonEmptyBlockCount = 0;
        tickingBlockCount = 0;

        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    int id = storage.getBlockTypeId(x, y, z);

                    if (id > 0) {
                        if (Block.byId[id] == null) {
                            storage.setBlockTypeId(x, y, z, (short) 0);
                        } else {
                            nonEmptyBlockCount++;
                            if (Block.byId[id].isTicking()) {
                                tickingBlockCount++;
                            }
                        }
                    }
                }
            }
        }
    }

    public byte[] g() {
        byte[] blockIds = new byte[4096];
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    blockIds[y << 8 | z << 4 | x] = (byte) (storage.getBlockTypeId(x, y, z) & 0xFF);
                }
            }
        }

        return blockIds;
    }

    public NibbleArray i() {
        NibbleArray extBlockIds = new NibbleArray(4096, 4);
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    extBlockIds.a(x, y, z, storage.getBlockTypeId(x, y, z) >> 8);
                }
            }
        }

        return extBlockIds;
    }

    public NibbleArray j() {
        NibbleArray blockData = new NibbleArray(4096, 4);
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    blockData.a(x, y, z, storage.getBlockData(x, y, z));
                }
            }
        }

        return blockData;
    }

    public NibbleArray k() {
        NibbleArray blockLight = new NibbleArray(4096, 4);
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    blockLight.a(x, y, z, storage.getBlockEmittedLight(x, y, z));
                }
            }
        }

        return blockLight;
    }

    public NibbleArray l() {
        NibbleArray skyLight = new NibbleArray(4096, 4);
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    skyLight.a(x, y, z, storage.getBlockSkyLight(x, y, z));
                }
            }
        }

        return skyLight;
    }

    public void a(byte[] blockIds) {
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    storage.setBlockTypeId(x, y, z, blockIds[y << 8 | z << 4 | x]);
                }
            }
        }
    }

    public void a(NibbleArray extBlockIds) {
        // Don't hang on to an empty nibble array
        boolean empty = true;
        for (int i = 0; i < extBlockIds.a.length; i++) {
            if (extBlockIds.a[i] != 0) {
                empty = false;
                break;
            }
        }

        if (empty) {
            return;
        }

        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    int id = extBlockIds.a(x, y, z) << 8 | storage.getBlockTypeId(x, y, z);
                    storage.setBlockTypeId(x, y, z, (short) (id & 0xFFF));
                }
            }
        }
    }

    public void b(NibbleArray blockData) {
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    storage.setBlockData(x, y, z, (byte) blockData.a(x, y, z));
                }
            }
        }
    }

    public void c(NibbleArray blockLight) {
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    storage.setBlockEmittedLight(x, y, z, (byte) blockLight.a(x, y, z));
                }
            }
        }
    }

    public void d(NibbleArray skyLight) {
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; y++) {
                for (int z = 0; z < 16; z++) {
                    storage.setBlockSkyLight(x, y, z, (byte) skyLight.a(x, y, z));
                }
            }
        }
    }
}

Palette.java

package org.bukkit.craftbukkit.util;

public class Palette {
    public static final int REAL_DATA_MASK = 0xFFFFFF;

    public static final int DATA_SHIFT = 12;
    public static final int EMITTEDLIGHT_SHIFT = DATA_SHIFT + 4;
    public static final int SKYLIGHT_SHIFT = EMITTEDLIGHT_SHIFT + 4;
    public static final int COUNT_SHIFT = SKYLIGHT_SHIFT + 4;

    // This is 4096 + 1 because of the default palette entry
    public static final int MAX_SIZE = 4097;
    // Default value of air with full skylight and full usage count
    private static final int DEFAULT_VALUE = 0 | (0 << DATA_SHIFT) | (0 << EMITTEDLIGHT_SHIFT) | (15 << SKYLIGHT_SHIFT) | (255 << COUNT_SHIFT);

    // Pointers to block storage, one per block in the chunk section
    private byte[] blocks = new byte[2048];
    // Format data is stored in the blocks array: 0 is nibble, 1 is unsigned byte, 2 is short
    private byte format = 0;

    // Actual block storage
    private int palette[] = new int[16];
    // Actual number of entries in the palette
    private int size = 0;
    // Sorted index into the above storage
    private short index[] = new short[16];
    // Position of last entry we stored in the palette
    private int lastEntry = 0;

    public Palette() {
        // Fill in our empty palette entry with some sane defaults
        palette[0] = DEFAULT_VALUE;
        index[0] = 0;
        size = 1;
    }

    public int getSize() {
        return size;
    }

    public short getBlockTypeId(int x, int y, int z) {
        return (short) (getRawData(x, y, z) & 0xFFF);
    }

    public byte getBlockData(int x, int y, int z) {
        return (byte) (getRawData(x, y, z) >>> DATA_SHIFT & 0xF);
    }

    public byte getBlockEmittedLight(int x, int y, int z) {
        return (byte) (getRawData(x, y, z) >>> EMITTEDLIGHT_SHIFT & 0xF);
    }

    public byte getBlockSkyLight(int x, int y, int z) {
        return (byte) (getRawData(x, y, z) >>> SKYLIGHT_SHIFT & 0xF);
    }

    public boolean setBlockTypeId(int x, int y, int z, short id) {
        int raw = getRawData(x, y, z);
        if ((raw & 0xFFF) == id) {
            return false;
        }

        setRawData(x, y, z, (raw & ~0xFFF) | (id & 0xFFF));
        return true;
    }

    public boolean setBlockData(int x, int y, int z, byte data) {
        int raw = getRawData(x, y, z);
        if ((raw >>> DATA_SHIFT & 0xF) == data) {
            return false;
        }

        setRawData(x, y, z, (raw & ~(0xF << DATA_SHIFT)) | ((data & 0xF) << DATA_SHIFT));
        return true;
    }

    public boolean setBlockEmittedLight(int x, int y, int z, byte light) {
        int raw = getRawData(x, y, z);
        if ((raw >>> EMITTEDLIGHT_SHIFT & 0xF) == light) {
            return false;
        }

        setRawData(x, y, z, (raw & ~(0xF << EMITTEDLIGHT_SHIFT)) | ((light & 0xF) << EMITTEDLIGHT_SHIFT));
        return true;
    }

    public boolean setBlockSkyLight(int x, int y, int z, byte light) {
        int raw = getRawData(x, y, z);
        if ((raw >>> SKYLIGHT_SHIFT & 0xF) == light) {
            return false;
        }

        setRawData(x, y, z, (raw & ~(0xF << SKYLIGHT_SHIFT)) | ((light & 0xF) << SKYLIGHT_SHIFT));
        return true;
    }

    public int getRawData(int x, int y, int z) {
        return getRawData(x, y, z, true);
    }

    private int getRawData(int x, int y, int z, boolean mask) {
        int blockPosition = getBlockPosition(x, y, z);
        int palettePosition = 0;

        switch (format) {
            case 0:
                palettePosition = getBlockNibble(blockPosition);
                break;
            case 1:
                // Treat byte as unsigned
                palettePosition = blocks[blockPosition] & 0xFF;
                break;
            case 2:
                // Get short from two bytes
                blockPosition *= 2;
                palettePosition = ((blocks[blockPosition + 1] & 0xFF) << 8) | (blocks[blockPosition] & 0xFF);
                break;
        }

        if (mask) {
            return palette[palettePosition] & REAL_DATA_MASK;
        }

        return palette[palettePosition];
    }

    public void setRawData(int x, int y, int z, int data) {
        int entryPosition = getEntryPosition(data);
        if (entryPosition == -1) {
            // Palette is full so this entry is not shared with other blocks so we can change it
            int old = getRawData(x, y, z, false);
            entryPosition = findEntry(old);
            palette[entryPosition] = incrementUsageCount(data);
            lastEntry = entryPosition;
            sortPalette();
            return;
        }

        int blockPostion = getBlockPosition(x, y, z);

        // We decrement the old palette entry this block pointed to so it can be reused
        switch (format) {
            case 0:
                palette[getBlockNibble(blockPostion)] = decrementUsageCount(palette[getBlockNibble(blockPostion)]);
                setBlockNibble(blockPostion, (byte) entryPosition);
                break;
            case 1:
                palette[blocks[blockPostion] & 0xFF] = decrementUsageCount(palette[blocks[blockPostion] & 0xFF]);
                // Treat byte as unsigned
                blocks[blockPostion] = (byte) (entryPosition & 0xFF);
                break;
            case 2:
                blockPostion *=2;
                // Store short in two bytes
                palette[((blocks[blockPostion + 1] & 0xFF) << 8) | (blocks[blockPostion] & 0xFF)] =  decrementUsageCount(palette[((blocks[blockPostion + 1] & 0xFF) << 8) | (blocks[blockPostion] & 0xFF)]);
                blocks[blockPostion + 1] = (byte) (((short) entryPosition) >>> 8);
                blocks[blockPostion] = (byte) (((short) entryPosition) & 0xFF);
                break;
        }
    }

    // Finds entry in the palette or creates new entry and returns the position
    private int getEntryPosition(int data) {
        // First, see if this data matches the last entry we stored
        if ((palette[lastEntry] & REAL_DATA_MASK) == (data & REAL_DATA_MASK)) {
            palette[lastEntry] = incrementUsageCount(palette[lastEntry]);
            return lastEntry;
        }

        // See if this data already exists in the palette
        int pos = findEntry(data);
        if ((palette[pos] & REAL_DATA_MASK) == (data & REAL_DATA_MASK)) {
            palette[pos] = incrementUsageCount(palette[pos]);
            lastEntry = pos;
            return pos;
        }

        // See if the position we got is for an unused entry
        if ((palette[pos] >>> COUNT_SHIFT & 0xFF) == 0) {
            palette[pos] = incrementUsageCount(data);
            lastEntry = pos;
            // We modified the palette so have to sort it again
            sortPalette();
            return pos;
        }

        // See if we've got any room left
        if (size >= MAX_SIZE) {
            compressPalette();
            if (size >= MAX_SIZE) {
                // We're still full after a compress run, each entry in the palette only belongs to a
                // single block. Return a special value to mark this fact.
                return -1;
            }
        }

        // Ensure our block array is large enough to hold our new position
        if (format == 0 && size == 16 || format == 1 && size == 256) {
            resizeBlockArray();
        }

        // Ensure our palette is large enough to hold the new entry
        if (palette.length == size) {
            int storageSize = Math.min(1 + palette.length + palette.length / 2, MAX_SIZE);
            int[] newPalette = new int[storageSize];
            System.arraycopy(palette, 0, newPalette, 0, palette.length);
            palette = newPalette;
            short[] newIndex = new short[storageSize];
            System.arraycopy(index, 0, newIndex, 0, index.length);
            index = newIndex;
        }

        // Store our new entry and return the position
        palette[size] = incrementUsageCount(data);
        index[size] = (short) size;
        lastEntry = size;
        sortPalette();
        ++size;

        return size - 1;
    }

    // Does a binary search to find the data or a slot marked as empty in the palette
    private int findEntry(int data) {
        int min = 0;
        int mid;
        int max = size - 1;

        do {
            mid = (min + max) / 2;
            // See if this slot is empty
            if ((palette[index[mid]] >>> COUNT_SHIFT & 0xFF) == 0) {
                return index[mid];
            }

            // Continue search
            if ((data & REAL_DATA_MASK) > (palette[index[mid]] & REAL_DATA_MASK)) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        } while (((data & REAL_DATA_MASK) != (palette[index[mid]] & REAL_DATA_MASK)) && (min <= max));

        return index[mid];
    }

    // Uses an insertion sort to sort the index, should be efficient as only one entry needs sorting
    private void sortPalette() {
        // Sort normally starts with 1 but we use 2 because the first entry is reserved
        for (int i = 2; i < size; i++) {
            int hole;
            short key = index[i];
            // Moving smaller entries up, lower bound is 1 instead of 0 because the first entry is reserved
            for(hole = i - 1; (hole >= 1) && ((palette[index[hole]] & REAL_DATA_MASK) > (palette[key] & REAL_DATA_MASK)); hole--) {
                index[hole + 1] = index[hole];
            }
            index[hole + 1] = key;
        }
    }

    // Generates new Palette object then copies the data over to this one to discard unused entries
    // Note: This is slow and should not be called often
    private void compressPalette() {
        Palette compressed = new Palette();
        for (int x = 0; x < 16; x++) {
            for (int y = 0; y < 16; x++) {
                for (int z = 0; z < 16; z++) {
                    compressed.setRawData(x, y, z, getRawData(x, y, z));
                }
            }
        }

        blocks = compressed.blocks;
        format = compressed.format;
        palette = compressed.palette;
        size = compressed.size;
        index = compressed.index;
        lastEntry = compressed.lastEntry;
    }

    private void resizeBlockArray() {
        byte[] newBlocks;

        switch (format) {
            case 0:
                newBlocks = new byte[4096];
                for (int i = 0; i < 4096; i++) {
                    newBlocks[i] = getBlockNibble(i);
                }
                blocks = newBlocks;
                format = 1;
                break;
            case 1:
                newBlocks = new byte[8192];
                for (int i = 0; i < 4096; i++) {
                    int pos = i * 2;
                    newBlocks[pos] = blocks[i];
                }
                blocks = newBlocks;
                format = 2;
                break;
            case 2:
                throw new IllegalStateException("Cannot resize block palette, at full size!");
        }
    }

    private int incrementUsageCount(int data) {
        int count = (data >>> COUNT_SHIFT) & 0xFF;
        count = Math.min(++count, 255);
        return (data & ~(0xFF << COUNT_SHIFT)) | ((count & 0xFF) << COUNT_SHIFT);
    }

    private int decrementUsageCount(int data) {
        // If the count is 255 we don't decrement as we consider this a permanent entry
        int count = (data >>> COUNT_SHIFT) & 0xFF;
        if (count == 255) {
            return data;
        }

        count = Math.max(--count, 0);
        return (data & ~(0xFF << COUNT_SHIFT)) | ((count & 0xFF) << COUNT_SHIFT);
    }

    private int getBlockPosition(int x, int y, int z) {
        return y << 8 | z << 4 | x;
    }

    private byte getBlockNibble(int pos) {
        int slot = pos >>> 1;
        int part = pos & 1;

        if (part == 0) {
            return (byte) (blocks[slot] & 0xF);
        } else {
            return (byte) ((blocks[slot] >>> 4) & 0xF);
        }
    }

    private void setBlockNibble(int pos, byte value) {
        int slot = pos >> 1;
        int part = pos & 1;

        if (part == 0) {
            blocks[slot] = (byte) ((blocks[slot] & 0xF0) | (value & 0xF));
        } else {
            blocks[slot] = (byte) ((blocks[slot] & 0x0F) | ((value & 0xF) << 4));
        }
    }
}