BlockhashQuick.cs

public static byte[] ComputeHashQuickParallel5<TPixel>(int bits, IImageBase<TPixel> image, ArrayPool<ulong> arrayPool)
    where TPixel : struct, IPixel<TPixel>
{
    //if (bits % 4 != 0) throw new ArgumentException();
    //if (image.Width % bits != 0 || image.Height % bits != 0) throw new ArgumentException();

    ulong[] blocks = null, medians = null;

    try
    {
        var blockWidth = image.Width / bits;
        var blockHeight = image.Height / bits;
        var blocksLength = bits * bits;
        var groupSize = blocksLength / 4;
        var parallelOptions = image.Configuration.ParallelOptions;
        blocks = arrayPool.Rent(blocksLength);

        Parallel.For(0, blocksLength, parallelOptions, blockIndex =>
        {
            var xStart = (blockIndex * blockWidth) % image.Width;
            var xEnd = xStart + blockWidth;

            var yStart = ((blockIndex * blockWidth) / image.Width) * blockHeight;
            var yEnd = yStart + blockHeight;

            ulong blockValue = 0;
            var pixels = image.Pixels;
            Rgba32 pixel = default;

            for (var y = yStart; y < yEnd; y++)
            {
                var baseIndex = image.Width * y;

                for (var x = xStart; x < xEnd; x++)
                {
                    pixels[baseIndex + x].ToRgba32(ref pixel);
                    blockValue += pixel.A == 0
                        ? 255UL * 3
                        : (ulong)pixel.R + pixel.G + pixel.B;
                }
            }

            blocks[blockIndex] = blockValue;
        });

        medians = arrayPool.Rent(4);

        Parallel.For(0, 4, parallelOptions, groupIndex =>
        {
            var heapCapacity = groupSize / 2 + 1;
            var heapArray = arrayPool.Rent(heapCapacity);

            try
            {
                var heap = new RestrictedBinaryHeap<ulong>(heapArray);
                var blockIndex = groupIndex * groupSize;
                var pushEnd = blockIndex + heapCapacity;
                var blockEnd = blockIndex + groupSize;

                for (; blockIndex < pushEnd; blockIndex++)
                    heap.Push(blocks[blockIndex]);

                for (; blockIndex < blockEnd; blockIndex++)
                {
                    var block = blocks[blockIndex];
                    if (block < heap.GetHead())
                        heap.ReplaceHead(block);
                }

                // note: これも公式 C 実装とは違う
                medians[groupIndex] = groupSize % 2 == 0
                    ? (heap.GetHead() + heap.GetSecond()) / 2
                    : heap.GetHead();
            }
            finally
            {
                arrayPool.Return(heapArray);
            }
        });

        // note: 公式 C 実装では 256
        var h = 255 * 3 * (ulong)blockWidth * (ulong)blockHeight / 2;
        var result = new byte[bits * bits / 8];

        for (var groupIndex = 0; groupIndex < 4; groupIndex++)
        {
            var med = medians[groupIndex];

            var blockIndex = groupIndex * groupSize;
            var blockEnd = blockIndex + groupSize;

            for (; blockIndex < blockEnd; blockIndex++)
            {
                var block = blocks[blockIndex];
                if (block > med || (block == med && med > h))
                    result[blockIndex / 8] |= (byte)(1 << (7 - blockIndex % 8));
            }
        }

        return result;
    }
    finally
    {
        if (blocks != null) arrayPool.Return(blocks);
        if (medians != null) arrayPool.Return(medians);
    }
}

internal struct RestrictedBinaryHeap<T> where T : IComparable<T>
{
    private readonly T[] _array;
    private int _count;

    public RestrictedBinaryHeap(int capacity)
    {
        this._array = new T[capacity];
        this._count = 0;
    }

    public RestrictedBinaryHeap(T[] array)
    {
        this._array = array;
        this._count = 0;
    }

    public void Push(T value)
    {
        var nodeIndex = this._count++;

        while (nodeIndex > 0)
        {
            var parentIndex = (nodeIndex - 1) / 2;

            if (value.CompareTo(this._array[parentIndex]) <= 0) break;

            this._array[nodeIndex] = this._array[parentIndex];
            nodeIndex = parentIndex;
        }

        this._array[nodeIndex] = value;
    }

    public void ReplaceHead(T value)
    {
        var nodeIndex = 0;

        while (true)
        {
            var childIndex = 2 * nodeIndex + 1;

            if (childIndex >= this._count) break;

            if (childIndex + 1 < this._count && this._array[childIndex + 1].CompareTo(this._array[childIndex]) > 0)
                childIndex++;

            if (value.CompareTo(this._array[childIndex]) >= 0) break;

            this._array[nodeIndex] = this._array[childIndex];
            nodeIndex = childIndex;
        }

        this._array[nodeIndex] = value;
    }

    public T GetHead() => this._array[0];

    public T GetSecond() => this._count < 3 || this._array[1].CompareTo(this._array[2]) >= 0
        ? this._array[1] : this._array[2];
}