<commit_before>#define NOMINMAX
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include "avisynth.h"
#include <math.h>
#include <assert.h>
#include <stdint.h>
#include <algorithm>
#include <emmintrin.h>
#include "special.h"


enum class InstructionSet
{
    SSE2,
    PLAIN_C
};

template<typename T>
static __forceinline void add_16_bins_c(T* a, const T *b) {
    for (int i = 0; i < 16; ++i) {
        a[i] += b[i];
    }
}

template<typename T>
static __forceinline void sub_16_bins_c(T* a, const T *b) {
    for (int i = 0; i < 16; ++i) {
        a[i] -= b[i];
    }
}

template<typename T>
static __forceinline void zero_single_bin_c(T* a) {
    for (int i = 0; i < 16; ++i) {
        a[i] = 0;
    }
}

template<typename T>
static __forceinline void add_16_bins_sse2(T* a, const T *b) {
    for (int i = 0; i < sizeof(T); ++i) {
        __m128i aval = _mm_load_si128(reinterpret_cast<const __m128i*>(a)+i);
        __m128i bval = _mm_load_si128(reinterpret_cast<const __m128i*>(b)+i);
        __m128i sum = _mm_adds_epu16(aval, bval);
        _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, sum);
    }
}

template<typename T>
static __forceinline void sub_16_bins_sse2(T* a, const T *b) {
    for (int i = 0; i < sizeof(T); ++i) {
        __m128i aval = _mm_load_si128(reinterpret_cast<const __m128i*>(a)+i);
        __m128i bval = _mm_load_si128(reinterpret_cast<const __m128i*>(b)+i);
        __m128i sum = _mm_subs_epu16(aval, bval);
        _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, sum);
    }
}

template<typename T>
static __forceinline void zero_single_bin_sse2(T* a) {
    __m128i zero = _mm_setzero_si128();
    for (int i = 0; i < sizeof(T); ++i) {
        _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, zero);
    }
}

template<InstructionSet instruction_set, typename T>
static __forceinline void add_16_bins(T* a, const T *b) {
    if (instruction_set == InstructionSet::SSE2) {
        add_16_bins_sse2(a, b);
    } else {
        add_16_bins_c(a, b);
    }
}

template<InstructionSet instruction_set, typename T>
static __forceinline void sub_16_bins(T* a, const T *b) {
    if (instruction_set == InstructionSet::SSE2) {
        sub_16_bins_sse2(a, b);
    } else {
        sub_16_bins_c(a, b);
    }
}

template<InstructionSet instruction_set, typename T>
static __forceinline void zero_single_bin(T* a) {
    if (instruction_set == InstructionSet::SSE2) {
        zero_single_bin_sse2(a);
    } else {
        zero_single_bin_c(a);
    }
}

static __forceinline int calculate_window_side_length(int radius, int x, int width) {
    int length = radius + 1;
    if (x <= radius) {
        length += x;
    } else if (x >= width-radius) {
        length += width-x-1;
    } else {
        length += radius;
    }
    return length;
}

template<typename T, InstructionSet instruction_set>
struct MedianProcessor
{
    typedef struct {
        T coarse[16];
        T fine[256];
    } Histogram;

    typedef struct {
        int start;
        int end;
    } ColumnPair;

    static const int HISTOGRAM_SIZE = sizeof(Histogram);

    static void calculate_median(uint8_t* dstp, const uint8_t* srcp, int dst_pitch, int src_pitch, int width, int height, int radius, void *buffer) {
        Histogram* histograms = reinterpret_cast<Histogram*>(buffer);
        __declspec(align(16)) Histogram current_hist;
        ColumnPair fine_columns[16]; //indexes of last and first column in every fine histogram segment
        memset(histograms, 0, width * HISTOGRAM_SIZE);

        //init histograms
        for (int y = 0; y < radius+1; ++y) {
            for (int x = 0; x < width; ++x) {
                uint8_t new_element = srcp[y*src_pitch+x];
                histograms[x].coarse[new_element>>4]++;
                histograms[x].fine[new_element]++;
            }
        }

        for (int y = 0; y < height; ++y) {
            int current_length_y = calculate_window_side_length(radius, y, height);

            memset(current_hist.coarse, 0, HISTOGRAM_SIZE);
            memset(fine_columns, -1, sizeof(fine_columns));
            //init histogram of the leftmost column
            for (int x = 0; x < radius; ++x) {
                add_16_bins<instruction_set>(current_hist.coarse, histograms[x].coarse);
            }

            for (int x = 0; x < width; ++x) {
                //add one column to the right
                if (x < (width-radius)) {
                    add_16_bins<instruction_set>(current_hist.coarse, histograms[x+radius].coarse);
                }

                int current_length_x = calculate_window_side_length(radius, x, width);
                int start_x = std::max(0, x-radius);
                int end_x = start_x + current_length_x;
                int half_elements = (current_length_y * current_length_x + 1) / 2;

                //finding median on coarse level
                int count = 0;
                int coarse_idx = -1;
                while (count < half_elements) {
                    count += current_hist.coarse[++coarse_idx];
                }
                count -= current_hist.coarse[coarse_idx];

                assert(coarse_idx < 16);
                int fine_offset = coarse_idx*16;

                //partially updating fine histogram
                if (fine_columns[coarse_idx].end < start_x) {
                    //any data we gathered is useless, drop it and build the whole block from scratch
                    zero_single_bin<instruction_set>(current_hist.fine + fine_offset);

                    for (int i = start_x; i < end_x; ++i) {
                        add_16_bins<instruction_set>(current_hist.fine+fine_offset, histograms[i].fine+fine_offset);
                    }
                } else {
                    int i = fine_columns[coarse_idx].start;
                    while (i < start_x) {
                        sub_16_bins<instruction_set>(current_hist.fine+fine_offset, histograms[i++].fine+fine_offset);
                    }
                    i = fine_columns[coarse_idx].end;
                    while (++i < end_x) {
                        add_16_bins<instruction_set>(current_hist.fine+fine_offset, histograms[i].fine+fine_offset);
                    }
                }
                fine_columns[coarse_idx].start = start_x;
                fine_columns[coarse_idx].end = end_x-1;

                //finding median on fine level
                int fine_idx = fine_offset - 1;
                while (count < half_elements) {
                    count += current_hist.fine[++fine_idx];
                }

                assert(fine_idx < 256);
                dstp[x] = fine_idx;

                //subtract leftmost histogram
                if (x >= radius) {
                    sub_16_bins<instruction_set>(current_hist.coarse, histograms[x-radius].coarse);
                }
            }

            //updating column histograms
            if (y >= radius) {
                for (int x = 0; x < width; ++x) {
                    uint8_t old_element = srcp[(y-radius)*src_pitch+x];
                    histograms[x].coarse[old_element>>4]--;
                    histograms[x].fine[old_element]--;<commit_msg>Put functions inside MedianProcessor class to remove some templating support code<commit_after>#define NOMINMAX
#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include "avisynth.h"
#include <math.h>
#include <assert.h>
#include <stdint.h>
#include <algorithm>
#include <emmintrin.h>
#include "special.h"


enum class InstructionSet
{
    SSE2,
    PLAIN_C
};

static __forceinline int calculate_window_side_length(int radius, int x, int width) {
    int length = radius + 1;
    if (x <= radius) {
        length += x;
    } else if (x >= width-radius) {
        length += width-x-1;
    } else {
        length += radius;
    }
    return length;
}

template<typename T, InstructionSet instruction_set>
class MedianProcessor
{
    typedef struct {
        T coarse[16];
        T fine[256];
    } Histogram;

    typedef struct {
        int start;
        int end;
    } ColumnPair;

    static __forceinline void add_16_bins_c(T* a, const T *b) {
        for (int i = 0; i < 16; ++i) {
            a[i] += b[i];
        }
    }

    static __forceinline void sub_16_bins_c(T* a, const T *b) {
        for (int i = 0; i < 16; ++i) {
            a[i] -= b[i];
        }
    }

    static __forceinline void zero_single_bin_c(T* a) {
        for (int i = 0; i < 16; ++i) {
            a[i] = 0;
        }
    }

    static __forceinline void add_16_bins_sse2(T* a, const T *b) {
        for (int i = 0; i < sizeof(T); ++i) {
            __m128i aval = _mm_load_si128(reinterpret_cast<const __m128i*>(a)+i);
            __m128i bval = _mm_load_si128(reinterpret_cast<const __m128i*>(b)+i);
            __m128i sum = _mm_adds_epu16(aval, bval);
            _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, sum);
        }
    }

    static __forceinline void sub_16_bins_sse2(T* a, const T *b) {
        for (int i = 0; i < sizeof(T); ++i) {
            __m128i aval = _mm_load_si128(reinterpret_cast<const __m128i*>(a)+i);
            __m128i bval = _mm_load_si128(reinterpret_cast<const __m128i*>(b)+i);
            __m128i sum = _mm_subs_epu16(aval, bval);
            _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, sum);
        }
    }

    static __forceinline void zero_single_bin_sse2(T* a) {
        __m128i zero = _mm_setzero_si128();
        for (int i = 0; i < sizeof(T); ++i) {
            _mm_store_si128(reinterpret_cast<__m128i*>(a)+i, zero);
        }
    }

    static __forceinline void add_16_bins(T* a, const T *b) {
        if (instruction_set == InstructionSet::SSE2) {
            add_16_bins_sse2(a, b);
        } else {
            add_16_bins_c(a, b);
        }
    }

    static __forceinline void sub_16_bins(T* a, const T *b) {
        if (instruction_set == InstructionSet::SSE2) {
            sub_16_bins_sse2(a, b);
        } else {
            sub_16_bins_c(a, b);
        }
    }

    static __forceinline void zero_single_bin(T* a) {
        if (instruction_set == InstructionSet::SSE2) {
            zero_single_bin_sse2(a);
        } else {
            zero_single_bin_c(a);
        }
    }

public:
    static const int HISTOGRAM_SIZE = sizeof(Histogram);

    static void calculate_median(uint8_t* dstp, const uint8_t* srcp, int dst_pitch, int src_pitch, int width, int height, int radius, void *buffer) {
        Histogram* histograms = reinterpret_cast<Histogram*>(buffer);
        __declspec(align(16)) Histogram current_hist;
        ColumnPair fine_columns[16]; //indexes of last and first column in every fine histogram segment
        memset(histograms, 0, width * HISTOGRAM_SIZE);

        //init histograms
        for (int y = 0; y < radius+1; ++y) {
            for (int x = 0; x < width; ++x) {
                uint8_t new_element = srcp[y*src_pitch+x];
                histograms[x].coarse[new_element>>4]++;
                histograms[x].fine[new_element]++;
            }
        }

        for (int y = 0; y < height; ++y) {
            int current_length_y = calculate_window_side_length(radius, y, height);

            memset(current_hist.coarse, 0, HISTOGRAM_SIZE);
            memset(fine_columns, -1, sizeof(fine_columns));
            //init histogram of the leftmost column
            for (int x = 0; x < radius; ++x) {
                add_16_bins(current_hist.coarse, histograms[x].coarse);
            }

            for (int x = 0; x < width; ++x) {
                //add one column to the right
                if (x < (width-radius)) {
                    add_16_bins(current_hist.coarse, histograms[x+radius].coarse);
                }

                int current_length_x = calculate_window_side_length(radius, x, width);
                int start_x = std::max(0, x-radius);
                int end_x = start_x + current_length_x;
                int half_elements = (current_length_y * current_length_x + 1) / 2;

                //finding median on coarse level
                int count = 0;
                int coarse_idx = -1;
                while (count < half_elements) {
                    count += current_hist.coarse[++coarse_idx];
                }
                count -= current_hist.coarse[coarse_idx];

                assert(coarse_idx < 16);
                int fine_offset = coarse_idx*16;

                //partially updating fine histogram
                if (fine_columns[coarse_idx].end < start_x) {
                    //any data we gathered is useless, drop it and build the whole block from scratch
                    zero_single_bin(current_hist.fine + fine_offset);

                    for (int i = start_x; i < end_x; ++i) {
                        add_16_bins(current_hist.fine+fine_offset, histograms[i].fine+fine_offset);
                    }
                } else {
                    int i = fine_columns[coarse_idx].start;
                    while (i < start_x) {
                        sub_16_bins(current_hist.fine+fine_offset, histograms[i++].fine+fine_offset);
                    }
                    i = fine_columns[coarse_idx].end;
                    while (++i < end_x) {
                        add_16_bins(current_hist.fine+fine_offset, histograms[i].fine+fine_offset);
                    }
                }
                fine_columns[coarse_idx].start = start_x;
                fine_columns[coarse_idx].end = end_x-1;

                //finding median on fine level
                int fine_idx = fine_offset - 1;
                while (count < half_elements) {
                    count += current_hist.fine[++fine_idx];
                }

                assert(fine_idx < 256);
                dstp[x] = fine_idx;

                //subtract leftmost histogram
                if (x >= radius) {
                    sub_16_bins(current_hist.coarse, histograms[x-radius].coarse);
                }
            }

            //updating column histograms
            if (y >= radius) {
                for (int x = 0; x < width; ++x) {
                    uint8_t old_element = srcp[(y-radius)*src_pitch+x];
                    histograms[x].coarse[old_element>>4]--;
                    histograms[x].fine[old_element]--;
{'fraction_non_alphanumeric': 0.11152520919766543, 'fraction_numerical': 0.023627030447929118, 'mean_word_length': 1.9311624072547404, 'pattern_counts': {'":': 0, '<': 93, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3797394', 'n_tokens_mistral': 5033, 'n_tokens_neox': 4494, 'n_words': 1030}