Rust: Create array from function at compilation

Question

I am looking for a solution to translate the following c++ function to Rust

    uint32_t reverseBits(uint32_t n) {
        static constexpr array<uint8_t, 256> table{[]() constexpr{
                constexpr size_t SIZE = 256;
                array<uint8_t, SIZE> result{};

                for (size_t i = 0; i < SIZE; ++i)
                    result[i] = (i * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff;
                return result;
        }()};

However:

• I cannot use #![feature(const_fn)] because #![feature] may not be used on the stable release channel.
• I cannot use build.rs and cargo either
• I thought about using macro_rules! but I cannot find a very simple example to precompute in a loop like:

for (size_t i = 0; i < SIZE; ++i)
   result[i] = (i * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff; // reverse bits

NB: My attemp to translate the full c++ code to Rust, with the table unfortunately computed at runtime:

    pub fn reverse_bits(x: u32) -> u32 {
        let table: [u32; 256];

        for i in 0..10 {
            table[i] = ((i as u64 * 0x0202020202 as u64 & 0x010884422010 as u64) % 0x3ff) as u32;
        }

        return (table[x & 0xff] << 24) | (table[(x >> 8) & 0xff] << 16) |
            (table[(x >> 16) & 0xff] << 8) | (table[(x >> 24) & 0xff]);
    }

also running into the type[u32] cannot be indexed by u32...

I anyone knows how I could build an array, at compile time, with 256 u32 values where each values is equal to (index * 0x0202020202ULL & 0x010884422010ULL) % 0x3ff; it would be very helpful!

Answer 1

I cannot use #![feature(const_fn)] because #![feature] may not be used on the stable release channel.

Well, I have good news for you: const fn has been part of stable Rust for quite a while now, so you can use it. But it will require some adjustments to the code.

First, you need to fix the issues that have nothing to do with const. As the error message tells you, you need to cast to usize to index an array. Your array should be initialized to 0 (which the C++ code actually does), and should be mut.

Then, to make it const fn, you need to replace the for loop (which is not yet allowed in const fn) with tail recursion, i.e. change:

for i in 0..10 {
    table[i] = ...;
}

to something like:

const fn set_table(mut table: [u32; 256], i: usize) -> [u32; 256] {
    if i == 10 {
        return table;
    }
    table[i] = ...;
    return set_table(table, i + 1);
}
table = set_table(table, 0);

Note that we have to pass the ownership of the table to the tail-recursive function and get it back from it because mutable references are not supported in const fn.

Finally, the C++ code uses a nice constant for SIZE, which we can do in Rust as well. The final result looks like this and builds using stable Rust on the playground:

pub const fn reverse_bits(x: u32) -> u32 {
    const SIZE: usize = 256;
    let mut table = [0u32; SIZE];

    const fn set_table(mut table: [u32; SIZE], i: usize) -> [u32; SIZE] {
        if i == SIZE {
            return table;
        }
        table[i] = ((i as u64 * 0x0202020202 & 0x010884422010) % 0x3ff) as u32;
        return set_table(table, i + 1);
    }
    table = set_table(table, 0);

    return (table[(x & 0xff) as usize] << 24)
        | (table[((x >> 8) & 0xff) as usize] << 16)
        | (table[((x >> 16) & 0xff) as usize] << 8)
        | (table[((x >> 24) & 0xff) as usize]);
}

Answer 2

A macro you should not use

I thought about using macro_rules! but I cannot find a very simple example to precompute in a loop

You can't just loop from 0 to 256 in a declarative macro because macros only know about the presence or absence of tokens, not their values. But there are other ways to approach these kinds of problems. Here's a macro that generates an array literal suitable for assignment to [u32; 256]:

macro_rules! table {
    () => { table!(@ (do re mi fa sol la ti do) 0u64) };
    (@ ($_:tt $($bin:tt)*) $($etc:expr),*) => {
        table!(@ ($($bin)*) $($etc*2, $etc*2 + 1),*)
    };
    (@ () $($i:expr),*) => {
        [$((($i * 0x0202020202 & 0x010884422010) % 0x3ff) as u32),*]
    };
}

This macro works in stages. When called without arguments (the first branch), it calls itself (the second branch) with a parenthesized sequence of 8 tokens and an increasing integer sequence initially containing just the one value 0u64. (The parenthesized tokens don't matter, as long as there are exactly 8 of them.) It recursively calls itself (still in the second branch) for each token in the list, doubling the length of the integer sequence with each token consumed. After 8 doublings (2⁸ = 256), the parentheses are empty and when it calls itself again (the third branch), it wraps each integer $i in (($i * 0x0202020202 & 0x010884422010) % 0x3ff) as u32 and puts the whole thing between square brackets.

Here it is on the Rust Playground. You can check the generated code by expanding macros. It's... surprisingly not that hard to understand, if you recognize the binary encoding of the integers. But I would recommend against using it in real code, because it is non-obvious. Use const evaluation instead when you can.

A more realistic macro-based answer

Generate the trivial, easy-to-verify part with your editor or preferred scripting language and use the macro for the repetitive part.

macro_rules! table {
    ($($i:expr,)*) => {
        [$((($i as u64 * 0x0202020202 & 0x010884422010) % 0x3ff) as u32),*]
    };
}
const TABLE: [u32; 256] = table![
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
    0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
    0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
    0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
    0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
    0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
];

Answer 3

For leetcode only (old compiler from 2019...)

I had to do it in two steps:

Generate the output locally

const SIZE: usize = 256;

const fn set_table(mut table: [u32; SIZE], i: usize) -> [u32; SIZE] {
        if i == SIZE {
            return table;
        }
        table[i] = ((i as u64 * 0x0202020202 & 0x010884422010) % 0x3ff) as u32;
        return set_table(table, i + 1);
    }


fn main() {
    let mut table = [0u32; SIZE];
    table = set_table(table, 0);

    for x in 0..table.len() {
         print!("{:#x}, ", table[x]);
         if x % 16 == 15 {
            println!("");
        }
    }
}

Copy paste the raw value of the output to build my array

impl Solution {
    pub const fn reverse_bits(x: u32) -> u32 {
    const table: [u32; 256] = [0x0, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 
0x8, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 
0x4, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 
0xc, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 
0x2, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 
0xa, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 
0x6, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 
0xe, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 
0x1, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 
0x9, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 
0x5, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 
0xd, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 
0x3, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 
0xb, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 
0x7, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 
0xf, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff];

    return (table[(x & 0xff) as usize] << 24)
        | (table[((x >> 8) & 0xff) as usize] << 16)
        | (table[((x >> 16) & 0xff) as usize] << 8)
        | (table[((x >> 24) & 0xff) as usize]);
    }
}

Obviously @trentcl and @user4815162342 methods are much better... if the compiler allows it.

NB: To check the result I used the following (thanks to this link):

let n:u32 = 43;
println!("{:#034b}", n);
let res:u32 = reverse_bits(n);
println!("{:#034b}", res);