Blog: Beyond De Bruijn: fast binary logarithm of a 10-bit number: debruijn.cpp

File debruijn.cpp, 2.1 KB (added by sam, 5 years ago)
Line 
1//
2// Copyright: (c) 2012 Sam Hocevar <sam@hocevar.net>
3//   This program is free software; you can redistribute it and/or
4//   modify it under the terms of the Do What The Fuck You Want To
5//   Public License, Version 2, as published by Sam Hocevar. See
6//   http://sam.zoy.org/projects/COPYING.WTFPL for more details.
7//
8
9#include <cstdio>
10#include <stdint.h>
11
12/* Size of the De Bruijn-like multiplier */
13typedef uint32_t input_t;
14
15/* How many bits are used to address the LUT */
16#define BITS 4
17
18/* Our list of constraints */
19struct s { input_t src; int dst; } constraints[] =
20{
21    { 0x001, 0, },
22    { 0x003, 1, },
23    { 0x007, 2, },
24    { 0x00f, 3, },
25    { 0x01f, 4, },
26    { 0x03f, 5, },
27    { 0x07f, 6, },
28    { 0x0ff, 7, },
29    { 0x1fe, 8, },
30    { 0x1ff, 8, },
31    { 0x3fc, 9, },
32    { 0x3fd, 9, },
33    { 0x3fe, 9, },
34    { 0x3ff, 9, },
35};
36
37#define NCONSTRAINTS (sizeof(constraints) / sizeof(*constraints))
38#define TABLESIZE (1 << BITS)
39#define SHIFT (sizeof(input_t) * 8 - BITS)
40
41int main(void)
42{
43    struct { input_t key; int dst; } p[TABLESIZE];
44    for (int i = 0; i < TABLESIZE; i++)
45    {
46        p[i].key = 0;
47        p[i].dst = 0;
48    }
49
50    for (input_t x = 1; x < (input_t)-1; )
51    {
52        for (int i = 0; i < NCONSTRAINTS; i++)
53        {
54            input_t m = (input_t)(constraints[i].src * x) >> SHIFT;
55            if (p[m].key == x && p[m].dst != constraints[i].dst)
56                goto fail;
57            p[m].key = x;
58            p[m].dst = constraints[i].dst;
59        }
60
61        printf("int p[] = { ");
62        for (int j = 0; j < TABLESIZE; j++)
63        {
64            for (int i = 0; i < NCONSTRAINTS; )
65            {
66                input_t m = (input_t)(constraints[i].src * x) >> SHIFT;
67                if (j == m)
68                {
69                    printf("%u, ", constraints[i].dst);
70                    break;
71                }
72                if (++i == NCONSTRAINTS)
73                    printf("-1, ");
74            }
75        }
76        printf("}; x = 0x%xu;\n", x);
77        break;
78
79fail:
80        if (x++ == (input_t)-1)
81        {
82            printf("No luck. Try to increase BITS?\n");
83        }
84    }
85}
86