LzwEncoder using ByteArrayEqualityComparer

LzwEncoder.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace SimpleGif.GifCore
{
    internal sealed class ByteArrayEqualityComparer : IEqualityComparer<byte[]>
    {
        public bool Equals(byte[] x, byte[] y)
        {
            if (x.Length != y.Length)
                return false;
            
            for (int i = 0; i < x.Length; i++)
            {
                if (x[i] != y[i])
                    return false;
            }

            return true;
        }

        public int GetHashCode(byte[] obj)
        {
            int hash = obj.Length;
            for (int i = 0; i < obj.Length; i++)
                hash = unchecked(hash * 314159 + obj[i]);

            return hash;
        }
    }
    
    internal static class ByteArrayHelper
    {
        public static byte[] MakeCopy(this byte[] bytes)
        {
            var newBytes = new byte[bytes.Length];
            Buffer.BlockCopy(bytes, 0, newBytes, 0, bytes.Length);
            return newBytes;
        }
    }

    internal sealed class CodeBuilder
    {
        private readonly List<byte[]> _temp;

        public CodeBuilder(int capacity = 8)
        {
            _temp = new List<byte[]>(capacity);

            for (int i = 0; i < capacity; i++)
                _temp.Add(new byte[i + 1]);
        }

        public byte[] Build(byte[] code, byte append)
        {
            while (code.Length >= _temp.Count)
                _temp.Add(new byte[_temp.Count + 1]);

            var tmp = _temp[code.Length];
            Buffer.BlockCopy(code, 0, tmp, 0, code.Length);
            tmp[code.Length] = append;
            return tmp;
        }
    }

    internal sealed class BitList
    {
        private readonly List<byte> _bytes;
        private byte _currentByte;
        private int _currentBit;

        public BitList(int capacity = 0)
        {
            _bytes = new List<byte>(capacity);
        }

        public void Add(int key, int codeSize)
        {
            int size = Math.Min(8 - _currentBit, codeSize);
            SetBits(ref _currentByte, _currentBit, size, key);
            _currentBit += size;

            if (_currentBit == 8)
            {
                _bytes.Add(_currentByte);
                _currentBit = 0;
                _currentByte = 0;

                int left = codeSize - size;
                if (left > 0)
                    Add(GetBits(key, size, left), left);
            }
        }

        private static int GetBits(int mask, int offset, int length)
        {
            return ((mask >> offset) & ((1 << length) - 1));
        }

        private static void SetBits(ref byte mask, int offset, int length, int value)
        {
            mask = (byte)((mask & ~(((1 << length) - 1) << offset)) | (value << offset));
        }

        public byte[] GetBytes()
        {
            if (_currentBit != 0)
            {
                _bytes.Add(_currentByte);
                _currentBit = 0;
                _currentByte = 0;
            }

            return _bytes.ToArray();
        }
    }

    internal static class LzwEncoder
    {
        public static byte GetMinCodeSize(byte[] colorIndexes)
        {
            byte minCodeSize = 2;
            var max = colorIndexes.Max();

            while (1 << minCodeSize <= max)
            {
                minCodeSize++;
            }

            return minCodeSize;
        }

        private static readonly byte[][] _CodeCache = Enumerable.Range(0, 256).Select(b => new[] { (byte)b }).ToArray();
        private static readonly ThreadLocal<CodeBuilder> _CodeBuilder = new ThreadLocal<CodeBuilder>(() => new CodeBuilder());

        public static byte[] Encode(byte[] colorIndexes, int minCodeSize)
        {
            var codeBuilder = _CodeBuilder.Value;

            var dict = new Dictionary<byte[], int>(4096, new ByteArrayEqualityComparer());
            var dictAdditionalSize = 2 + (1 << minCodeSize);

            var clearCode = 1 << minCodeSize;
            var endOfInformation = clearCode + 1;
            var code = _CodeCache[colorIndexes[0]];
            var codeSize = minCodeSize + 1;
            var bits = new BitList((codeSize + 3) * colorIndexes.Length);

            bits.Add(clearCode, codeSize);

            for (var i = 1; i < colorIndexes.Length; i++)
            {
                var next = codeBuilder.Build(code, colorIndexes[i]);
                if (dict.ContainsKey(next))
                {
                    code = next;
                }
                else
                {
                    if (code.Length == 1)
                        bits.Add(code[0], codeSize);
                    else
                        bits.Add(dict[code], codeSize);

                    code = _CodeCache[colorIndexes[i]];

                    if (dict.Count + dictAdditionalSize < 4096)
                    {
                        dict.Add(next.MakeCopy(), dict.Count + dictAdditionalSize);

                        if (dict.Count + dictAdditionalSize -1 == 1 << codeSize)
                        {
                            codeSize++;
                        }
                    }
                }
            }

            if (code.Length == 1)
                bits.Add(code[0], codeSize);
            else
                bits.Add(dict[code], codeSize);

            bits.Add(endOfInformation, codeSize);

            var bytes = bits.GetBytes();

            return bytes;
        }
    }
}