<commit_before>/**
 * hdr_histogram.c
 * Written by <NAME> and released to the public domain,
 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
 */

#define __STDC_CONSTANT_MACROS
#define __STDC_LIMIT_MACROS

#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>

#if defined(_MSC_VER)
#include <intrin.h>
#else
#include <inttypes.h>
#endif

#include "hdr_histogram.hpp"

inline int32_t hdr_clz64(uint64_t x) {
#if defined(_MSC_VER)
#  if defined(_M_AMD64)
  return (int32_t)__lzcnt64(x);
#  else
  // On 32-bit this needs to be split into two operations
  int32_t lz = (int32_t)__lzcnt((unsigned long)(x >> 32));
  if (lz == 32) {
    // Scan the last 32 bits by truncating the 64-bit value
    return (int32_t)__lzcnt((unsigned long)x) + 32;
  }
  return lz;
#  endif
#else
  return (int32_t)__builtin_clzll(x);
#endif
}

//  ######   #######  ##     ## ##    ## ########  ######
// ##    ## ##     ## ##     ## ###   ##    ##    ##    ##
// ##       ##     ## ##     ## ####  ##    ##    ##
// ##       ##     ## ##     ## ## ## ##    ##     ######
// ##       ##     ## ##     ## ##  ####    ##          ##
// ##    ## ##     ## ##     ## ##   ###    ##    ##    ##
//  ######   #######   #######  ##    ##    ##     ######

static int32_t normalize_index(struct hdr_histogram* h, int32_t index)
{
    if (h->normalizing_index_offset == 0)
    {
        return index;
    }

    int32_t normalized_index = index - h->normalizing_index_offset;
    int32_t adjustment = 0;

    if (normalized_index < 0)
    {
        adjustment = h->counts_len;
    }
    else if (normalized_index >= h->counts_len)
    {
        adjustment = -h->counts_len;
    }

    return normalized_index + adjustment;
}

static int64_t counts_get_direct(struct hdr_histogram* h, int32_t index)
{
    return h->counts[index];
}

static int32_t counts_get_normalised(struct hdr_histogram* h, int32_t index)
{
    return (int32_t)counts_get_direct(h, normalize_index(h, index));
}

static void counts_inc_normalised(
    struct hdr_histogram* h, int32_t index, int64_t value)
{
    int32_t normalised_index = normalize_index(h, index);
    h->counts[normalised_index] += value;
    h->total_count += value;
}

static void counts_set_direct(struct hdr_histogram* h, int32_t index, int64_t value)
{
    h->counts[index] = value;
}

static void counts_set_normalised(struct hdr_histogram* h, int32_t index, int64_t value)
{
    int32_t normalised_index = normalize_index(h, index);
    counts_set_direct(h, normalised_index, value);
}

static void counts_set_min_max(struct hdr_histogram* h, int64_t min, int64_t max)
{
    h->min_value = min;
    h->max_value = max;
}

static void update_min_max(struct hdr_histogram* h, int64_t value)
{
    h->min_value = (value < h->min_value && value != 0) ? value : h->min_value;
    h->max_value = (value > h->max_value) ? value : h->max_value;
}

// ##     ## ######## #### ##       #### ######## ##    ##
// ##     ##    ##     ##  ##        ##     ##     ##  ##
// ##     ##    ##     ##  ##        ##     ##      ####
// ##     ##    ##     ##  ##        ##     ##       ##
// ##     ##    ##     ##  ##        ##     ##       ##
// ##     ##    ##     ##  ##        ##     ##       ##
//  #######     ##    #### ######## ####    ##       ##

static int64_t power(int64_t base, int64_t exp)
{
    int result = 1;
    while(exp)
    {
        result *= (int)base; exp--;
    }
    return result;
}

static int32_t get_bucket_index(struct hdr_histogram* h, int64_t value)
{
    int32_t pow2ceiling = 64 - hdr_clz64(value | h->sub_bucket_mask); // smallest power of 2 containing value
    return pow2ceiling - (int32_t)h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1);
}

static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude)
{
    return (int32_t)(value >> (bucket_index + unit_magnitude));
}
<commit_msg>Replace LZCNT with BSR instruction in hdr_histogram<commit_after>/**
 * hdr_histogram.c
 * Written by <NAME> and released to the public domain,
 * as explained at http://creativecommons.org/publicdomain/zero/1.0/
 */

#define __STDC_CONSTANT_MACROS
#define __STDC_LIMIT_MACROS

#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>

#if defined(_MSC_VER)
#include <intrin.h>
#else
#include <inttypes.h>
#endif

#include "hdr_histogram.hpp"

/**
 * Get the most significant bit set.
 *
 * The result is a one-based index, zero means no bits are set.
 */
inline int32_t hdr_bsr64(uint64_t x) {
#if defined(_MSC_VER)
  unsigned long index;
#  if defined(_M_AMD64)
  char isNonzero = _BitScanReverse64(&index, x);
  if (isNonzero)
    return index + 1;
  else
    return 0;
#  else
  // On 32-bit this needs to be split into two operations
  const char isNonzero = _BitScanReverse(&index, (unsigned long)(x >> 32));
  if (isNonzero)
    return index + 32 + 1;
  else {
    // Scan the last 32 bits by truncating the 64-bit value
    isNonzero = _BitScanReverse(&index, (unsigned long)x);
    if (isNonzero)
      return index + 1;
    else
      return 0;
  }
#  endif
#else
  return 64 - (int32_t)__builtin_clzll(x);
#endif
}

//  ######   #######  ##     ## ##    ## ########  ######
// ##    ## ##     ## ##     ## ###   ##    ##    ##    ##
// ##       ##     ## ##     ## ####  ##    ##    ##
// ##       ##     ## ##     ## ## ## ##    ##     ######
// ##       ##     ## ##     ## ##  ####    ##          ##
// ##    ## ##     ## ##     ## ##   ###    ##    ##    ##
//  ######   #######   #######  ##    ##    ##     ######

static int32_t normalize_index(struct hdr_histogram* h, int32_t index)
{
    if (h->normalizing_index_offset == 0)
    {
        return index;
    }

    int32_t normalized_index = index - h->normalizing_index_offset;
    int32_t adjustment = 0;

    if (normalized_index < 0)
    {
        adjustment = h->counts_len;
    }
    else if (normalized_index >= h->counts_len)
    {
        adjustment = -h->counts_len;
    }

    return normalized_index + adjustment;
}

static int64_t counts_get_direct(struct hdr_histogram* h, int32_t index)
{
    return h->counts[index];
}

static int32_t counts_get_normalised(struct hdr_histogram* h, int32_t index)
{
    return (int32_t)counts_get_direct(h, normalize_index(h, index));
}

static void counts_inc_normalised(
    struct hdr_histogram* h, int32_t index, int64_t value)
{
    int32_t normalised_index = normalize_index(h, index);
    h->counts[normalised_index] += value;
    h->total_count += value;
}

static void counts_set_direct(struct hdr_histogram* h, int32_t index, int64_t value)
{
    h->counts[index] = value;
}

static void counts_set_normalised(struct hdr_histogram* h, int32_t index, int64_t value)
{
    int32_t normalised_index = normalize_index(h, index);
    counts_set_direct(h, normalised_index, value);
}

static void counts_set_min_max(struct hdr_histogram* h, int64_t min, int64_t max)
{
    h->min_value = min;
    h->max_value = max;
}

static void update_min_max(struct hdr_histogram* h, int64_t value)
{
    h->min_value = (value < h->min_value && value != 0) ? value : h->min_value;
    h->max_value = (value > h->max_value) ? value : h->max_value;
}

// ##     ## ######## #### ##       #### ######## ##    ##
// ##     ##    ##     ##  ##        ##     ##     ##  ##
// ##     ##    ##     ##  ##        ##     ##      ####
// ##     ##    ##     ##  ##        ##     ##       ##
// ##     ##    ##     ##  ##        ##     ##       ##
// ##     ##    ##     ##  ##        ##     ##       ##
//  #######     ##    #### ######## ####    ##       ##

static int64_t power(int64_t base, int64_t exp)
{
    int result = 1;
    while(exp)
    {
        result *= (int)base; exp--;
    }
    return result;
}

static int32_t get_bucket_index(struct hdr_histogram* h, int64_t value)
{
    int32_t pow2ceiling = hdr_bsr64(value | h->sub_bucket_mask); // smallest power of 2 containing value
    return pow2ceiling - (int32_t)h->unit_magnitude - (h->sub_bucket_half_count_magnitude + 1);
}

static int32_t get_sub_bucket_index(int64_t value, int32_t bucket_index, int32_t unit_magnitude)
{
    return (int32_t)(value >> (bucket_index + unit_magnitude));
}

{'fraction_non_alphanumeric': 0.17637151106833493, 'fraction_numerical': 0.026106833493743986, 'mean_word_length': 2.589378238341969, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 75, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7142801', 'n_tokens_mistral': 3201, 'n_tokens_neox': 3033, 'n_words': 595}