1

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!

Improve this question
0

3 Answers 3

Reset to default
2

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]);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Thanks a lot @user4815162342, really appreciate your help however it does not compile: if i == SIZE --> loops and conditional expressions are not stable in const fn, and compiler recommending to use !feature(const_fn)
@AntoninGAVREL Have you checked the playground link, where I tested it to compile on stable? Perhaps you are using an older version of Rust?
I am compiling from leetcode.com/problems/reverse-bits
Leetcode uses Rust 1.40 apparently. They're a bit out of date.
also, very minor question, but when I want to get the string display the number with bits reverse, the MSB is skipped, play.rust-lang.org/… any solution for this?
|
1

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 (28 = 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,
];
Improve this answer

2 Comments

very nice, it still doesnt work on leetcode but appreciate your effort. Also do not use such click bait title, you know that when something is forbidden you create more attraction ;)
Hm. I tested it with Rust 1.40 in Compiler Explorer and it seems fine. Maybe leetcode isn't using that version after all? The same strategy should work all the way back to 1.2.0 if you replace $_ with $_b (not sure when that change was made)
1

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);
Improve this answer

2 Comments

If you generate the output locally, then you no longer need the function to be const fn and can ditch the tail recursion. In other words, you can just write for i in 0..SIZE { table[i] = ... } directly in main().
I agree with your comment (the general idea) but on algorithm platforms the goals - one of, along with memory - is to have the lowest runtime that is why I get my array locally and then I copy-paste it on the algorithm platform. Anyways many thanks for your answer :) I really like it!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.