<commit_before>#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <algorithm>

int64_t r(int64_t min, int64_t max) {
    int64_t n1 = rand();
    int64_t n2 = rand();
    int64_t n3 = rand();
    n1 = n1 ^ (n2 << 16) ^ (n3 << 16);
    n1 = n1 % (max - min);
    n1 = n1 + min;
    return n1;
}

int64_t sdiv(int64_t a, int64_t b) {
  return (a - ((a % b) + b) % b) / b;
}

bool u_method_0(int den, int sh_post, int bits) {
    uint64_t max = (1L << bits) - 1;
    //for (int64_t num = 0; num <= max; num++) {	
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result >>= sh_post;
	if (num / den != result) return false;
    }
    return true;
}

bool u_method_1(int den, int64_t mul, int sh_post, int bits) {
    uint64_t max = (1L << bits) - 1;
    //for (uint64_t num = 0; num <= max; num++) {
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result *= mul;
	result >>= bits;
	if (result > max) return false;
	result >>= sh_post;                               
	if (num / den != result) return false;
    }
    return true;
}

bool u_method_2(int den, int64_t mul, int sh_post, int bits) {
    uint64_t max = (1UL << bits) - 1;
    //for (uint64_t num = 0; num <= max; num++) {
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result *= mul;
	result >>= bits;
	if (result > max) return false;
	result += (num - result)>>1;
	if (result > max) return false;
	result >>= sh_post;
	if (num / den != result) return false;
    }
    return true;    
}

bool s_method_0(int den, int sh_post, int bits) {
    int64_t min = -(1L << (bits-1)), max = (1L << (bits-1))-1;
    //for (int64_t num = min; num <= max; num++) {    
    for (int iter = 0; iter < 100000L; iter++) {
        int64_t num = r(min, max);
        // Make sure we hit the extremes
        if (iter == 0) num = min;
        if (iter == 1) num = max;
        int64_t result = num;
	result >>= sh_post;
	if (sdiv(num, den) != result) return false;
    }
    return true;
}

bool s_method_1(int den, int64_t mul, int sh_post, int bits) {
    int64_t min = -(1 << (bits-1)), max = (1 << (bits-1))-1;

    //for (int64_t num = min; num <= max; num++) {    
    for (int iter = 0; iter < 100000L; iter++) {
        int64_t num = r(min, max);
        // Make sure we hit the extremes
        if (iter == 0) num = min;
        if (iter == 1) num = max;
	int64_t result = num;
        uint64_t xsign = result >> (bits-1);
        uint64_t q0 = (mul * (xsign ^ result)) >> bits;
        result = xsign ^ (q0 >> sh_post);
	if (sdiv(num, den) != result) return false;
    }
    return true;    
}

int main(int argc, char **argv) {
    /* This program computes a table to help us do cheap integer
        division by a constant. It is based on the paper "Division by
        Invariant Integers using Multiplication" by Granlund and
        Montgomery.
    */

    printf("/** \\file \n"
           " * Tables telling us how to do integer division\n"
           " * via fixed-point multiplication for various small\n"
           " * constants. This file is automatically generated\n"
           " * by find_inverse.c\n"
           " */\n"
           "#include <stdint.h>\n"
           "namespace Halide {\n"
           "namespace Internal {\n"
           "namespace IntegerDivision {\n\n");
    
    for (int bits = 8; bits <= 32; bits *= 2) {
	printf("int64_t table_u%d[][3] = {\n", bits);
	for (int den = 2; den <= 256; den++) {
	    for (int shift = 0; shift < 16; shift++) {
		if (u_method_0(den, shift, bits)) {
		    printf("    {0, 0, %d},\n", shift);
		    goto next_unsigned;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {
                int64_t mul = (1L << (bits+shift)) / den + 1;
                if (u_method_1(den, mul, shift, bits)) {
                    printf("    {1, %lldLL, %d},\n", mul, shift);
                    goto next_unsigned;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {
                int64_t mul = (1L << (bits+shift+1)) / den - (1L << bits) + 1;
                if (u_method_2(den, mul, shift, bits)) {
                    printf("    {2, %ldL, %d},\n", mul, shift);
                    goto next_unsigned;
		}
	    }
	    printf("ERROR! No solution found for unsigned %d\n", den);
	  next_unsigned:;
	}
	printf("};\n");
	printf("int64_t table_s%d[][3] = {\n", bits);
	for (int den = 2; den <= 256; den++) {

	    for (int shift = 0; shift < 8; shift++) {
		if (s_method_0(den, shift, bits)) {
		    printf("    {0, 0, %d},\n", shift);
		    goto next_signed;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {                
                int64_t mul = (1L << (shift + bits)) / den + 1;
                if (s_method_1(den, mul, shift, bits)) {
                    printf("    {1, %ldL, %d},\n", mul, shift);
                    goto next_signed;
		}
	    }
	    printf("ERROR! No solution found for signed %d\n", den);
	  next_signed:;
	}
	printf("};\n");        
    }

    printf("}}}\n");

    return 0;
}
<commit_msg>Fix find_inverse.c so that it generates a correct table.<commit_after>#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <algorithm>

int64_t r(int64_t min, int64_t max) {
    int64_t n1 = rand();
    int64_t n2 = rand();
    int64_t n3 = rand();
    n1 = n1 ^ (n2 << 16) ^ (n3 << 16);
    n1 = n1 % (max - min);
    n1 = n1 + min;
    return n1;
}

int64_t sdiv(int64_t a, int64_t b) {
  return (a - ((a % b) + b) % b) / b;
}

bool u_method_0(int den, int sh_post, int bits) {
    uint64_t max = (1L << bits) - 1;
    //for (int64_t num = 0; num <= max; num++) {	
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result >>= sh_post;
	if (num / den != result) return false;
    }
    return true;
}

bool u_method_1(int den, int64_t mul, int sh_post, int bits) {
    uint64_t max = (1L << bits) - 1;
    //for (uint64_t num = 0; num <= max; num++) {
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result *= mul;
	result >>= bits;
	if (result > max) return false;
	result >>= sh_post;                               
	if (num / den != result) return false;
    }
    return true;
}

bool u_method_2(int den, int64_t mul, int sh_post, int bits) {
    uint64_t max = (1UL << bits) - 1;
    //for (uint64_t num = 0; num <= max; num++) {
    for (unsigned iter = 0; iter < 100000UL; iter++) {
        uint64_t num = r(0, max);
        // Make sure we hit the extremes
        if (iter == 0) num = 0;
        if (iter == 1) num = max;
	uint64_t result = num;
	result *= mul;
	result >>= bits;
	if (result > max) return false;
	result += (num - result)>>1;
	if (result > max) return false;
	result >>= sh_post;
	if (num / den != result) return false;
    }
    return true;    
}

bool s_method_0(int den, int sh_post, int bits) {
    int64_t min = -(1L << (bits-1)), max = (1L << (bits-1))-1;
    //for (int64_t num = min; num <= max; num++) {    
    for (int iter = 0; iter < 1000000L; iter++) {
        int64_t num = r(min, max);
        // Make sure we hit the extremes
        if (iter == 0) num = min;
        if (iter == 1) num = max;
        int64_t result = num;
	result >>= sh_post;
	if (sdiv(num, den) != result) return false;
    }
    return true;
}

bool s_method_1(int den, int64_t mul, int sh_post, int bits) {
    int64_t min = -(1 << (bits-1)), max = (1 << (bits-1))-1;

    //for (int64_t num = min; num <= max; num++) {    
    for (int iter = 0; iter < 1000000L; iter++) {
        int64_t num = r(min, max);
        // Make sure we hit the extremes
        if (iter == 0) num = min;
        if (iter == 1) num = max;
	int64_t result = num;
        uint64_t xsign = result >> (bits-1);
        uint64_t q0 = (mul * (xsign ^ result)) >> bits;
        result = xsign ^ (q0 >> sh_post);
	if (sdiv(num, den) != result) return false;
    }
    return true;    
}

int main(int argc, char **argv) {
    /* This program computes a table to help us do cheap integer
        division by a constant. It is based on the paper "Division by
        Invariant Integers using Multiplication" by Granlund and
        Montgomery.
    */

    printf("/** \\file \n"
           " * Tables telling us how to do integer division\n"
           " * via fixed-point multiplication for various small\n"
           " * constants. This file is automatically generated\n"
           " * by find_inverse.c\n"
           " */\n"
           "#include <stdint.h>\n"
           "namespace Halide {\n"
           "namespace Internal {\n"
           "namespace IntegerDivision {\n\n");
    
    for (int bits = 8; bits <= 32; bits *= 2) {
	printf("int64_t table_u%d[][3] = {\n", bits);
	for (int den = 2; den <= 256; den++) {
	    for (int shift = 0; shift < 16; shift++) {
		if (u_method_0(den, shift, bits)) {
		    printf("    {0, 0, %d},\n", shift);
		    goto next_unsigned;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {
                int64_t mul = (1L << (bits+shift)) / den + 1;
                if (u_method_1(den, mul, shift, bits)) {
                    printf("    {1, %lldLL, %d},\n", mul, shift);
                    goto next_unsigned;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {
                int64_t mul = (1L << (bits+shift+1)) / den - (1L << bits) + 1;
                if (u_method_2(den, mul, shift, bits)) {
                    printf("    {2, %ldL, %d},\n", mul, shift);
                    goto next_unsigned;
		}
	    }
	    printf("ERROR! No solution found for unsigned %d\n", den);
	  next_unsigned:;
	}
	printf("};\n");
	printf("int64_t table_s%d[][3] = {\n", bits);
	for (int den = 2; den <= 256; den++) {

	    for (int shift = 0; shift < 8; shift++) {
		if (s_method_0(den, shift, bits)) {
		    printf("    {0, 0, %d},\n", shift);
		    goto next_signed;
		}
	    }
	    
	    for (int shift = 0; shift < 8; shift++) {                
                int64_t mul = (1L << (shift + bits)) / den + 1;
                if (s_method_1(den, mul, shift, bits)) {
                    printf("    {1, %ldL, %d},\n", mul, shift);
                    goto next_signed;
		}
	    }
	    printf("ERROR! No solution found for signed %d\n", den);
	  next_signed:;
	}
	printf("};\n");        
    }

    printf("}}}\n");

    return 0;
}

{'fraction_non_alphanumeric': 0.16056414429075128, 'fraction_numerical': 0.039779405117078025, 'mean_word_length': 1.9241342849590273, 'pattern_counts': {'":': 0, '<': 103, '<?xml version=': 0, '>': 61, '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': '67827', 'n_tokens_mistral': 4348, 'n_tokens_neox': 3964, 'n_words': 1282}