Fast 2D DCT implementation for 32*32 array, but can be adapted for any fixed dimension. Inspired by the CocoaImageHashing impl for iOS.

Fast 2D DCT 32*32

package pro.labster.dct

import kotlin.math.cos
import kotlin.math.sqrt

/**
 * Around 20x faster than a naive implementation
 */
class DctAlgorithm2DFast : DctAlgorithm {

    private val coefficients = DoubleArray(DIMENSION)

    private val coefficients1 = Array(DIMENSION) { DoubleArray(DIMENSION) }
    private val coefficients2 = Array(DIMENSION) { DoubleArray(DIMENSION) }
    private val coefficientsV = Array(DIMENSION) { DoubleArray(DIMENSION) }

    init {
        coefficients.fill(1.0)
        coefficients[0] = 1.0 / sqrt(2.0)

        for (i in 0 until DIMENSION) {
            for (j in 0 until DIMENSION) {
                coefficients1[i][j] = cos((2 * i + 1.0) / DOUBLE_DIMENSION * j * Math.PI)
                coefficients2[i][j] = coefficients1[i][j]

                coefficientsV[i][j] = coefficients[i] * coefficients[j] / sqrt(2.0 * DIMENSION)
            }
        }
    }

    override fun apply(data: Array<DoubleArray>): Array<DoubleArray> {
        if (data.size != DIMENSION || data[0].size != DIMENSION) {
            throw IllegalArgumentException("Data dimension is not ${DIMENSION}x$DIMENSION")
        }

        val result = Array(DIMENSION) { DoubleArray(DIMENSION) }

        for (u in 0 until DIMENSION) {
            for (v in 0 until DIMENSION) {
                var sum = unrollDctI(data, coefficients1, coefficients2, u, v)

                sum *= coefficientsV[u][v]
                result[u][v] = sum
            }
        }

        return result
    }

    /**
     * Do NOT replace with for-loop, it would significantly slow down the algo implementation
     */
    private fun unrollDctI(data: Array<DoubleArray>, co1: Array<DoubleArray>, co2: Array<DoubleArray>, u: Int, v: Int): Double {
        var newSum = 0.0

        newSum = unrollDctJ(data, newSum, co1, co2, 0, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 1, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 2, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 3, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 4, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 5, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 6, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 7, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 8, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 9, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 10, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 11, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 12, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 13, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 14, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 15, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 16, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 17, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 18, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 19, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 20, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 21, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 22, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 23, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 24, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 25, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 26, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 27, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 28, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 29, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 30, u, v)
        newSum = unrollDctJ(data, newSum, co1, co2, 31, u, v)

        return newSum
    }

    /**
     * Do NOT replace with for-loop, it would significantly slow down the algo implementation
     */
    private fun unrollDctJ(data: Array<DoubleArray>, sum: Double, co1: Array<DoubleArray>, co2: Array<DoubleArray>, i: Int, u: Int, v: Int): Double {
        var newSum = sum

        newSum += inlineDctSum(data, co1, co2, i, u, 0, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 1, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 2, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 3, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 4, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 5, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 6, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 7, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 8, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 9, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 10, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 11, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 12, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 13, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 14, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 15, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 16, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 17, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 18, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 19, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 20, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 21, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 22, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 23, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 24, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 25, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 26, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 27, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 28, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 29, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 30, v)
        newSum += inlineDctSum(data, co1, co2, i, u, 31, v)

        return newSum
    }

    /**
     * Note: Inlining speeds it up 6x, don't blindly believe the linter. And yep, I've checked it, just believe me
     */
    private inline fun inlineDctSum(data: Array<DoubleArray>, co1: Array<DoubleArray>, co2: Array<DoubleArray>, i: Int, u: Int, j: Int, v: Int): Double {
        return co1[i][u] * co2[j][v] * data[i][j]
    }

    private companion object {
        private const val DIMENSION = 32
        private const val DOUBLE_DIMENSION = DIMENSION * 2
    }
}