I have a nice mathematical puzzle for you! The problem to solve is the following: Let's…
- User
I have a nice mathematical puzzle for you! The problem to solve is the following:
Let's say we have a bit-string of length 512, which we will call . Now, we will do a operation permutes the bits, followed by one that splits the bits sequentially into chunks of length 4. The chunking is performed as:
10011110...->[1001,1110,...]The goal is to produce a reversible mapping (a permutation) that will make sure that no chunk contains neighbouring bits. In the sense that, if we have a chunk with bits from positions[0,2,6,7], this is WRONG. We a looking for a mapping that will produce chunks such as:[0,3,6,20].Can you solve the puzzle and find a reversible mapping ?
Assistant
Okay, this is a fun puzzle! Let's break it down.
1. Understanding the Setup
- We have a bit string of length . The positions are indexed .
- A permutation rearranges the string into . Let be represented by a function which maps the position in the permuted string to the original position in . So, . Since is a permutation, is a bijection from to itself. Being a bijection means it's reversible.
- The permuted string is chunked into chunks, each of length 4.
- Chunk 0: positions
- Chunk 1: positions
- ...
- Chunk : positions
- ...
- Chunk 127: positions
- The Constraint: For any chunk , the set of original positions must not contain any pair of consecutive integers. That is, for any , we must have .
2. Strategy: Partitioning the Indices
The core of the problem is to find a way to group the original indices into 128 sets of 4, such that no set contains consecutive numbers. Let's call these sets .
Once we have such a partition, we can define the permutation . We want the indices that land in chunk (positions to ) to come from a specific set . The simplest way is to map the indices from set to the positions in chunk . So, we need .
3. Constructing the Partition
Let's try a structured approach. Consider the indices modulo 8. . This means we have 64 blocks of 8 indices: .
Within each block , let's create two sets of 4 indices:
- Set : Contains the even indices in the block: .
- Set : Contains the odd indices in the block: .
Let's check the constraint:
- In , the minimum difference between indices is 2 (e.g., ). So, no consecutive indices exist.
- In , the minimum difference between indices is also 2 (e.g., ). So, no consecutive indices exist.
This construction gives us 128 sets (), each containing 4 indices, and crucially, no set contains consecutive indices. This is exactly the partition we need.
4. Defining the Permutation
Now we map these sets to the chunks . Chunk corresponds to the positions . We want the set of original indices to be exactly .
We can achieve this by assigning the indices from to the positions in chunk and the indices from to the positions in chunk .
-
For even-numbered chunks (): The positions are , which is . The required original indices are . We define the mapping for these positions:
- The set of original indices . This satisfies the condition.
-
For odd-numbered chunks (): The positions are , which is . The required original indices are . We define the mapping for these positions:
- The set of original indices . This also satisfies the condition.
5. The Result
The mapping defined above is a permutation of . It rearranges the bits such that when the permuted string is chunked into blocks of 4, the set of original indices feeding into each chunk does not contain any adjacent pairs. This permutation defines the reversible mapping requested.
Summary of the Permutation :
The permutation maps position (in the permuted string) to the original position from which the bit originates. The definition is as follows:
For each block from to :
- Map positions to original positions .
- Map positions to original positions .
This specific permutation fulfills the requirements of the puzzle.
- User
Aha! Nice one. Could you explain if your result is generalizable where chunks are another power of 2? Let's say 8 or 16?
Assistant
Yes, absolutely! The strategy used for chunk size is indeed generalizable to other powers of 2, provided that the total length meets certain divisibility requirements.
Let's generalize the problem:
- String length .
- Chunk size , where . (Original case was , ).
- Number of chunks .
- Permutation maps position in the permuted string to original position .
- Constraint: For each chunk (positions to ), the set of original indices must not contain any pair of adjacent integers ( for any ).
The Generalized Strategy: Even/Odd Split within Larger Blocks
The core idea relies on partitioning the indices into sets that satisfy the constraint, and then mapping these sets to the output chunks. We can use blocks of size .
- Block Size: Choose blocks of size .
- Divisibility Condition: For this strategy to work seamlessly, the total length must be divisible by the block size .
- Number of Blocks: If is divisible by , we have blocks. Let's index these blocks by . Block covers the original indices from to .
- Partitioning within Blocks: Within each block , partition the indices into two sets, each of size :
- Set (Even Indices): Contains all the even indices within the block.
- Set (Odd Indices): Contains all the odd indices within the block.
- Constraint Check: In both and , the minimum difference between any two indices is 2. Therefore, neither set contains adjacent indices, satisfying the constraint.
- Total Sets: We create blocks, and each block creates 2 sets. This gives a total of sets. This matches the required number of chunks ().
- Mapping: We can map the original index sets () to the permuted string chunks (). A natural mapping is to associate the pairs of sets with pairs of chunks .
- For even chunks : These are the positions to , which simplifies to to . We map these positions to the original indices in set . A specific mapping rule is: for .
- For odd chunks : These are the positions to , which simplifies to to . We map these positions to the original indices in set . A specific mapping rule is: for .
Applying to and (with N=512):
-
Case k=8:
- . .
- Number of chunks .
- Block size .
- Divisibility Check: Is divisible by ? Yes, . We have 32 blocks.
- Block covers indices .
- Set (Even Indices): (8 indices).
- Set (Odd Indices): (8 indices).
- Mapping:
- Chunk (positions to ) maps to . for .
- Chunk (positions to ) maps to . for .
- This works.
-
Case k=16:
- . .
- Number of chunks .
- Block size .
- Divisibility Check: Is divisible by ? Yes, . We have 16 blocks.
- Block covers indices .
- Set (Even Indices): (16 indices).
- Set (Odd Indices): (16 indices).
- Mapping:
- Chunk (positions to ) maps to . for .
- Chunk (positions to ) maps to . for .
- This also works.
Conclusion
Yes, the strategy is generalizable. For a chunk size (where ), a reversible permutation (defined by ) exists as long as is divisible by . The permutation involves grouping indices into blocks of size , splitting each block into its even and odd indices (each subset having size and satisfying the non-adjacent constraint), and then mapping consecutive chunks to these corresponding index sets.
This holds true for since is divisible by in all these cases.
- User
Oke amazing! Then I have one more challenge for you! Given a vector
std::vector<uint64_t>;in C++ that stores these bits. Can you write the code to perform the permutation mapping as a functionpermutation_mapping()that generalizes your method for the case where the sequence is a power of 2 (256, 512, 1024, etc.) and the chunking is a power of 2 (4,8,16, etc.)? The code should be able to do the following:using Vec = std::vector<uint64_t>; const int chunk_size = ... // power of 2 const int L = ... // bit-string length, power of 2 and larger than chunk_size Vec bufA(L / 64); Vec *cur = &bufA; get_bitstring(*cur) permutation_mapping(*cur,chunk_size,L) Assistant
Okay, this is a great challenge! Implementing the generalized permutation logic in C++ requires careful handling of bit manipulation and vector indexing.
Here's the C++ code implementing the
permutation_mappingfunction based on the strategy we discussed.First, let's define the necessary helper functions for bit access and validation:
#include <vector> #include <cstdint> #include <cassert> // For assertions (optional, good for debugging) #include <algorithm> // For std::copy #include <stdexcept> // For exceptions like std::invalid_argument, std::out_of_range #include <cmath> // For std::abs in verification (if needed) // Define Vec as requested using Vec = std::vector<uint64_t>; // --- Helper Functions --- /** * @brief Checks if a non-negative integer is a power of two. * @param n The integer to check. * @return true if n is a power of two (and n > 0), false otherwise. */ bool is_power_of_two(int n) { // A power of two must be positive and have only one bit set. return (n > 0) && ((n & (n - 1)) == 0); } /** * @brief Retrieves the bit at a specific index from the bit string represented by the vector. * @param data The vector storing the bit string (as uint64_t chunks). * @param bit_index The index of the bit to retrieve (0-based). * @return The boolean value of the bit (true for 1, false for 0). * @throws std::out_of_range if bit_index is invalid. */ bool get_bit(const Vec& data, int bit_index) { // Ensure the bit_index is within the valid range of bits represented by the vector. size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("get_bit: bit_index is out of bounds."); } // Calculate which uint64_t word contains the bit. uint64_t word_index = bit_index / 64; // Calculate the position of the bit within that word. int bit_index_in_word = bit_index % 64; // Extract the bit using bitwise operations. return (data[word_index] >> bit_index_in_word) & 1; } /** * @brief Sets the bit at a specific index in the bit string represented by the vector. * @param data The vector storing the bit string (as uint64_t chunks). This vector is modified. * @param bit_index The index of the bit to set (0-based). * @param value The boolean value to set the bit to (true for 1, false for 0). * @throws std::out_of_range if bit_index is invalid. */ void set_bit(Vec& data, int bit_index, bool value) { // Ensure the bit_index is within the valid range of bits represented by the vector. size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("set_bit: bit_index is out of bounds."); } // Calculate which uint64_t word contains the bit. uint64_t word_index = bit_index / 64; // Calculate the position of the bit within that word. int bit_index_in_word = bit_index % 64; // Set or clear the bit using bitwise operations. if (value) { data[word_index] |= (1ULL << bit_index_in_word); // Set the bit } else { data[word_index] &= ~(1ULL << bit_index_in_word); // Clear the bit } } /** * @brief Calculates the original bit position from which a bit should be taken * to be placed at a given 'output_pos' after the permutation. * * This function implements the core logic of the permutation mapping (sigma): * sigma(output_pos) = original_pos * * The strategy partitions indices into blocks of size B = 2 * chunk_size. * Within each block b, it separates indices into even (G_{2b}) and odd (G_{2b+1}). * Even-indexed output chunks (C_{2b}) map to even original index sets (G_{2b}), * and odd-indexed output chunks (C_{2b+1}) map to odd original index sets (G_{2b+1}). * * @param output_pos The target position in the permuted bit string (0 to L-1). * @param chunk_size The size of each chunk (must be a power of 2, >= 4). * @param L The total length of the bit string (must be a power of 2). * @return The corresponding original bit position. */ int get_original_pos(int output_pos, int chunk_size, int L) { int k = chunk_size; int B = 2 * k; // The size of blocks used in the strategy. // Determine which chunk the current output position belongs to. // There are L/k chunks in total. int chunk_idx = output_pos / k; // Determine the offset of the current position within its chunk (0 to k-1). int offset_in_chunk = output_pos % k; int original_pos; // Check if the chunk index is even or odd. if (chunk_idx % 2 == 0) { // Even-indexed chunk (C_0, C_2, C_4, ...) maps to even-indexed original index sets (G_0, G_2, G_4, ...). // The sets G_{2b} contain even indices within block b: {2bk, 2bk+2, ..., 2bk+2k-2}. // The 'offset_in_chunk'-th element of G_{2b} is 2bk + 2 * offset_in_chunk. // We derive 'b' from the even chunk index: b = chunk_idx / 2. int b = chunk_idx / 2; original_pos = b * B + 2 * offset_in_chunk; } else { // Odd-indexed chunk (C_1, C_3, C_5, ...) maps to odd-indexed original index sets (G_1, G_3, G_5, ...). // The sets G_{2b+1} contain odd indices within block b: {2bk+1, 2bk+3, ..., 2bk+2k-1}. // The 'offset_in_chunk'-th element of G_{2b+1} is 2bk + 1 + 2 * offset_in_chunk. // We derive 'b' from the odd chunk index using integer division: b = chunk_idx / 2. int b = chunk_idx / 2; original_pos = b * B + 1 + 2 * offset_in_chunk; } // Sanity check: Ensure the calculated original position is within the bounds of the bit string. // This should hold true if the input parameters and logic are correct. if (original_pos < 0 || original_pos >= L) { // Throwing a logic error indicates an internal inconsistency. throw std::logic_error("Calculated original_pos is out of bounds. Check logic or input parameters."); } return original_pos; } /** * @brief Applies a permutation mapping to rearrange bits in a vector according to the puzzle's rules. * * The permutation rearranges the bits such that when the resulting bit string is * chunked sequentially into segments of size 'chunk_size', no segment contains bits * that were adjacent in the original string. * * This implementation uses a temporary buffer (O(L) space) to facilitate the permutation, * then copies the result back into the input vector ('data'), making it an effective in-place modification. * The time complexity is O(L). * * @param data The vector of uint64_t storing the bit string. This vector is modified in-place. * @param chunk_size The size of each chunk. Must be a power of 2 and >= 4. * @param L The total length of the bit string. Must be a power of 2. * * @throws std::invalid_argument if input parameters (chunk_size, L, or data size) do not meet the required constraints. */ void permutation_mapping(Vec& data, int chunk_size, int L) { // --- Input Validation --- // 1. chunk_size must be a power of 2 and at least 4. if (!is_power_of_two(chunk_size) || chunk_size < 4) { throw std::invalid_argument("permutation_mapping: chunk_size must be a power of 2 and >= 4."); } // 2. L must be a power of 2. if (!is_power_of_two(L)) { throw std::invalid_argument("permutation_mapping: L must be a power of 2."); } // 3. L must be greater than or equal to chunk_size. if (L < chunk_size) { throw std::invalid_argument("permutation_mapping: L must be greater than or equal to chunk_size."); } // 4. The strategy requires L to be divisible by 2 * chunk_size. // This ensures that we can form full blocks of size 2*chunk_size. int block_size = 2 * chunk_size; if (L % block_size != 0) { throw std::invalid_argument("permutation_mapping: L must be divisible by 2 * chunk_size for this strategy."); } // 5. Verify that the provided vector 'data' correctly represents L bits. // Each uint64_t holds 64 bits. if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("permutation_mapping: The size of the 'data' vector does not correspond to L bits."); } // --- Permutation Implementation --- // Create a temporary buffer to store the result of the permutation. // This is necessary because we need to read bits from original positions // while simultaneously writing the permuted bits. A direct in-place // swap/move is complex for bit manipulation and often less efficient. Vec temp_buf(data.size()); // Iterate through each possible output position 'i' in the permuted bit string. for (int i = 0; i < L; ++i) { // For the current output position 'i', determine the corresponding original bit position. int original_pos = get_original_pos(i, chunk_size, L); // Retrieve the bit value from the calculated original position in the input data. bool bit_value = get_bit(data, original_pos); // Place this retrieved bit value into the correct position 'i' in the temporary buffer. set_bit(temp_buf, i, bit_value); } // Once all bits have been processed and placed into the temporary buffer, // copy the contents of the temporary buffer back to the original 'data' vector. // This completes the in-place modification. std::copy(temp_buf.begin(), temp_buf.end(), data.begin()); } // --- Example Usage (Illustrative) --- /* // Placeholder function to simulate getting the bitstring data. // In a real scenario, this would load data from a source. void get_bitstring(Vec& data, int L) { if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("get_bitstring: Vector size mismatch with L."); } // Fill with a simple alternating pattern (101010...) for demonstration purposes. for (int i = 0; i < L; ++i) { set_bit(data, i, (i % 2) == 0); // Set bit to 1 if index is even, 0 if odd } } // Helper function for printing bits (useful for debugging/verification) void print_bits(const Vec& data, int L, const std::string& prefix = "") { std::cout << prefix; // Print only the first 64 bits for brevity, unless L is smaller. int print_limit = std::min(L, 64); for (int i = 0; i < print_limit; ++i) { std::cout << get_bit(data, i); } if (L > 64) { std::cout << "..."; } std::cout << std::endl; } // Verification function: checks if the resulting permutation satisfies the non-adjacent constraint. bool verify_permutation(const Vec& original_data, int chunk_size, int L) { // Create a copy to perform the permutation on, keeping the original intact for comparison/reference. Vec permuted_data = original_data; try { permutation_mapping(permuted_data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Verification Error: Failed to apply permutation: " << e.what() << std::endl; return false; } int k = chunk_size; int num_chunks = L / k; // Check each chunk for the adjacency constraint. for (int chunk_idx = 0; chunk_idx < num_chunks; ++chunk_idx) { std::vector<int> chunk_original_indices; // Store original indices feeding into this chunk. for (int offset = 0; offset < k; ++offset) { int output_pos = chunk_idx * k + offset; // Get the original position that maps to this output position. chunk_original_indices.push_back(get_original_pos(output_pos, chunk_size, L)); } // Check all pairs of original indices within this chunk for adjacency. for (size_t i = 0; i < chunk_original_indices.size(); ++i) { for (size_t j = i + 1; j < chunk_original_indices.size(); ++j) { if (std::abs(chunk_original_indices[i] - chunk_original_indices[j]) == 1) { // Found adjacent original indices within the same chunk. Constraint violated. std::cerr << "Verification Failed: Adjacent original indices found in chunk " << chunk_idx << " (Indices: " << chunk_original_indices[i] << ", " << chunk_original_indices[j] << ")" << std::endl; return false; } } } } // If no violations were found after checking all chunks, the permutation is valid. return true; } int main() { // Example Parameters: // L: Total bit string length (must be power of 2) // chunk_size: Size of each chunk (must be power of 2, >= 4) // Constraint: L must be divisible by (2 * chunk_size) for this strategy. // Test Case 1: L=512, chunk_size=4 { const int L = 512; const int chunk_size = 4; Vec data(L / 64); // Vector size is L/64 elements of uint64_t std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); // Populate the data vector print_bits(data, L, "Original data (first 64 bits): "); try { Vec original_data_copy = data; // Keep a copy for verification permutation_mapping(data, chunk_size, L); // Apply the permutation print_bits(data, L, "Permuted data (first 64 bits): "); // Verify the result if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } // Test Case 2: L=1024, chunk_size=8 { const int L = 1024; const int chunk_size = 8; Vec data(L / 64); std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); print_bits(data, L, "Original data (first 64 bits): "); try { Vec original_data_copy = data; permutation_mapping(data, chunk_size, L); print_bits(data, L, "Permuted data (first 64 bits): "); if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } // Test Case 3: L=512, chunk_size=256 (Edge case where L = 2 * chunk_size) { const int L = 512; const int chunk_size = 256; Vec data(L / 64); std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); print_bits(data, L, "Original data (first 64 bits): "); try { Vec original_data_copy = data; permutation_mapping(data, chunk_size, L); print_bits(data, L, "Permuted data (first 64 bits): "); if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } return 0; } */Explanation:
is_power_of_two(int n): A standard utility function to check if a number is a power of two. This is used for validatingchunk_sizeandL.get_bit(const Vec& data, int bit_index): This function isolates and returns the value of a single bit atbit_indexfrom thestd::vector<uint64_t>. It calculates the correctuint64_tword and the bit's position within that word.set_bit(Vec& data, int bit_index, bool value): This function modifies a single bit atbit_indexwithin the vector. It uses bitwise OR (|=) to set a bit to 1 and bitwise AND with a complemented mask (&= ~) to set it to 0.get_original_pos(int output_pos, int chunk_size, int L): This is the core logic function. It takes anoutput_pos(where a bit ends up in the permuted string) and calculates theoriginal_pos(where that bit came from). It uses the derived formulas based on chunk indices, offsets, and the block structure (B = 2 * chunk_size).permutation_mapping(Vec& data, int chunk_size, int L):- Validation: It first performs thorough checks on
chunk_size,L, and the relationship between them (Ldivisible by2 * chunk_size) to ensure the strategy is applicable and inputs are valid. It also checks if the vector size matchesL. - Temporary Buffer: It creates a
temp_bufof the same size asdatato store the permuted bits. This is crucial for correctly rearranging bits without corrupting data needed for subsequent calculations. - Permutation Loop: It iterates through every possible
output_posfrom0toL-1. - Bit Transfer: For each
output_pos, it finds the correspondingoriginal_posusingget_original_pos. It then fetches the bit fromdataatoriginal_posusingget_bitand places it intotemp_bufatoutput_posusingset_bit. - Final Copy: After the loop finishes,
temp_bufholds the correctly permuted bit string.std::copyis used to transfer this data back into the originaldatavector, effectively completing the operation in-place from the caller's perspective (though using O(L) auxiliary space).
- Validation: It first performs thorough checks on
This code provides a robust and general solution for the permutation mapping as described, adhering to the constraints and requirements. The example
mainfunction demonstrates how to use it and includes a verification step.- User
Very nice! Now, could you make this code as fast as possible? Things like multi-threading are not needed, but make it 🔥🔥🔥 if you can!
Assistant
Okay, let's crank up the performance! The key to making this fast lies in minimizing overhead, optimizing calculations, and improving memory access patterns where possible, even without multi-threading.
The main bottlenecks in the previous version were:
- Function Call Overhead: Calling
get_bitandset_bitfor every single bit. - Calculation Overhead: The formula for
get_original_posinvolves divisions and modulo operations. - Memory Access Pattern: Reading bits from scattered locations in the source
datavector is inherently slow due to cache misses (this is the main unavoidable cost). Writing totemp_bufis sequential, which is good.
Here's an optimized version focusing on these points:
Optimizations Implemented:
- Direct Bit Manipulation: Replaced
get_bitandset_bitcalls within the loop with inline bitwise operations. - Optimized Index Calculation: Replaced divisions and modulo operations involving
chunk_sizewith bit shifts and masks, using__builtin_ctz(or equivalent) to findlog2(chunk_size)efficiently. - Word-Oriented Processing: The main loop now iterates through the destination buffer (
temp_buf) word by word (uint64_t), processing 64 bits at a time. This improves cache locality for the destination writes and reduces loop overhead compared to a pure bit-by-bit loop. - Conditional Writes: Since
temp_bufis initialized to zeros, we only need to perform a write operation (|= (1ULL << bit_offset)) when the source bit is actually1. This can provide a speedup if the input bit string isn't entirely composed of ones. - Compiler Intrinsics: Used
__builtin_ctzll(for GCC/Clang) or_BitScanForward64(for MSVC) for efficient calculation oflog2(chunk_size).
#include <vector> #include <cstdint> #include <numeric> // Not strictly needed here but useful for other std:: algorithms #include <algorithm> // For std::copy, std::min #include <stdexcept> // For exceptions #include <iostream> // For error reporting and testing output // Include headers for compiler intrinsics if needed for __builtin_ctz or _BitScanForward64 #if defined(_MSC_VER) #include <intrin.h> // For _BitScanForward64 #pragma intrinsic(_BitScanForward64) // Enable intrinsic #endif // Define Vec as requested using Vec = std::vector<uint64_t>; // --- Helper Function for log2 (using count trailing zeros) --- /** * @brief Calculates the base-2 logarithm of a power-of-two integer. * Uses compiler intrinsics for maximum efficiency. * @param n The input integer (must be a power of two > 0). * @return The exponent k such that n = 2^k. */ inline int get_power_of_two_exponent(uint64_t n) { // Ensure n is indeed a power of two and positive before calling intrinsics. // The validation is done in the main function. #if defined(__GNUC__) || defined(__clang__) // __builtin_ctzll counts trailing zeros for unsigned long long (uint64_t) return __builtin_ctzll(n); #elif defined(_MSC_VER) // _BitScanForward64 finds the index of the least significant set bit unsigned long index; // The function returns non-zero if a bit was found, zero otherwise. // We assume n > 0 due to prior validation. _BitScanForward64(&index, n); return static_cast<int>(index); #else // Portable fallback (slower) if no compiler intrinsics are available int count = 0; while ((n & 1) == 0) { n >>= 1; count++; } return count; #endif } /** * @brief Applies a permutation mapping to rearrange bits in a vector, optimized for speed. * * This function implements the described permutation using efficient calculations * and optimized memory access patterns suitable for single-threaded execution. * It rearranges bits such that sequential chunking of the permuted string avoids * chunks containing bits from adjacent original positions. * * @param data The vector of uint64_t representing the bit string. This vector is modified in-place. * @param chunk_size The size of each chunk. Must be a power of 2 and >= 4. * @param L The total length of the bit string. Must be a power of 2. * * @throws std::invalid_argument if input parameters (chunk_size, L, data size) are invalid * or do not meet the requirements for the algorithm. */ void permutation_mapping_fast(Vec& data, int chunk_size, int L) { // --- Input Validation --- // Check if chunk_size is a power of 2 and at least 4 // (chunk_size & (chunk_size - 1)) == 0 checks for power of 2 if (chunk_size <= 0 || (static_cast<uint64_t>(chunk_size) & (static_cast<uint64_t>(chunk_size) - 1)) != 0 || chunk_size < 4) { throw std::invalid_argument("permutation_mapping_fast: chunk_size must be a power of 2 and >= 4."); } // Check if L is a positive power of 2 if (L <= 0 || (static_cast<uint64_t>(L) & (static_cast<uint64_t>(L) - 1)) != 0) { throw std::invalid_argument("permutation_mapping_fast: L must be a positive power of 2."); } // Check if L is large enough for the chunk size if (L < chunk_size) { throw std::invalid_argument("permutation_mapping_fast: L must be greater than or equal to chunk_size."); } // Check the core strategy requirement: L must be divisible by block_size (2 * chunk_size) int block_size = 2 * chunk_size; if (L % block_size != 0) { throw std::invalid_argument("permutation_mapping_fast: L must be divisible by 2 * chunk_size for this strategy."); } // Check if the provided vector's size corresponds correctly to L bits if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("permutation_mapping_fast: The size of the 'data' vector does not correspond to L bits."); } // --- Precomputations for Performance --- // Calculate log2(chunk_size). This exponent is used for efficient division/modulo by chunk_size. int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(chunk_size)); // Create a mask for efficient modulo operation: (chunk_size - 1) int k_mask = chunk_size - 1; size_t num_words = data.size(); // Create a temporary buffer to hold the permuted result. Initialize all bits to 0. Vec temp_buf(num_words, 0ULL); // --- Optimized Permutation Loop --- // Process the destination buffer word by word (64 bits at a time). for (size_t word_idx_dest = 0; word_idx_dest < num_words; ++word_idx_dest) { uint64_t current_dest_word = 0; // Accumulator for the bits of the current destination word // Calculate the starting bit index in the overall bit string for this destination word. int dest_word_start_bit = word_idx_dest * 64; // Iterate through each of the 64 bits within the current destination word. for (int bit_offset = 0; bit_offset < 64; ++bit_offset) { // Calculate the current output position in the permuted bit string. int output_pos = dest_word_start_bit + bit_offset; // --- Calculate the original source position (`original_pos`) --- // This section implements the core permutation logic derived earlier: // original_pos = (q / 2) * block_size + (q & 1) + (2 * r) // where q = output_pos / chunk_size, r = output_pos % chunk_size // Use bit shifts and masks for efficiency: // q = chunk index int q_val = output_pos >> k_exponent; // Equivalent to output_pos / chunk_size // r = offset within chunk int r_val = output_pos & k_mask; // Equivalent to output_pos % chunk_size // Calculate original_pos using the optimized formula int original_pos = ((q_val >> 1) * block_size) + (q_val & 1) + (2 * r_val); // --- Read the bit from the source 'data' vector --- // Determine the word index and bit index within that word for the source position. uint64_t word_idx_orig = original_pos / 64; int bit_idx_in_word_orig = original_pos % 64; // Extract the bit value from the source word. // We only need to know if the bit is set (1). // Using shift and bitwise AND is efficient. // Note: `1ULL << bit_idx_in_word_orig` creates a mask with only the target bit set. bool source_bit_is_set = ((data[word_idx_orig] >> bit_idx_in_word_orig) & 1ULL); // --- Set the bit in the destination word if the source bit was 1 --- if (source_bit_is_set) { // Set the corresponding bit in the current destination word accumulator. // The bit offset within the destination word is `bit_offset`. current_dest_word |= (1ULL << bit_offset); } } // Assign the fully constructed destination word to the temporary buffer. temp_buf[word_idx_dest] = current_dest_word; } // --- Copy the permuted data back to the original vector --- // This final copy operation takes O(L/64) time. std::copy(temp_buf.begin(), temp_buf.end(), data.begin()); } // --- Example Usage (Optional - for testing) --- /* #include <cmath> // For std::abs in verification // Helper to get a single bit (needed for verification and dummy get_bitstring) bool get_bit(const Vec& data, int bit_index) { size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("get_bit: bit_index is out of bounds."); } uint64_t word_index = bit_index / 64; int bit_index_in_word = bit_index % 64; return (data[word_index] >> bit_index_in_word) & 1; } // Helper to set a single bit (needed for dummy get_bitstring) void set_bit(Vec& data, int bit_index, bool value) { size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("set_bit: bit_index is out of bounds."); } uint64_t word_index = bit_index / 64; int bit_index_in_word = bit_index % 64; if (value) { data[word_index] |= (1ULL << bit_index_in_word); } else { data[word_index] &= ~(1ULL << bit_index_in_word); } } // Placeholder function to simulate getting the bitstring data. void get_bitstring(Vec& data, int L) { if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("get_bitstring: Vector size mismatch with L."); } // Fill with a simple alternating pattern (101010...) for demonstration. for (int i = 0; i < L; ++i) { set_bit(data, i, (i % 2) == 0); // Set bit to 1 if index is even } } // Helper function for printing bits (useful for debugging/verification) void print_bits(const Vec& data, int L, const std::string& prefix = "") { std::cout << prefix; // Print a reasonable number of bits, e.g., first 128, for visualization int print_limit = std::min(L, 128); for (int i = 0; i < print_limit; ++i) { std::cout << get_bit(data, i); } if (L > print_limit) { std::cout << "..."; } std::cout << std::endl; } // Verification function: checks if the resulting permutation satisfies the non-adjacent constraint. bool verify_permutation(const Vec& original_data, int chunk_size, int L) { Vec permuted_data = original_data; // Make a copy try { // Use the fast function for verification too permutation_mapping_fast(permuted_data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Verification Error: Failed to apply permutation: " << e.what() << std::endl; return false; } int k = chunk_size; int block_size = 2 * k; int num_chunks = L / k; // Re-calculate original indices for verification int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(k)); int k_mask = k - 1; // Check each chunk for the adjacency constraint. for (int chunk_idx = 0; chunk_idx < num_chunks; ++chunk_idx) { std::vector<int> chunk_original_indices; // Store original indices feeding into this chunk. for (int offset = 0; offset < k; ++offset) { int output_pos = chunk_idx * k + offset; // Calculate original_pos using the same logic as the permutation function int q_val = output_pos >> k_exponent; int r_val = output_pos & k_mask; int original_pos = ((q_val >> 1) * block_size) + (q_val & 1) + (2 * r_val); chunk_original_indices.push_back(original_pos); } // Check all pairs of original indices within this chunk for adjacency. for (size_t i = 0; i < chunk_original_indices.size(); ++i) { for (size_t j = i + 1; j < chunk_original_indices.size(); ++j) { if (std::abs(chunk_original_indices[i] - chunk_original_indices[j]) == 1) { // Found adjacent original indices within the same chunk. Constraint violated. std::cerr << "Verification Failed: Adjacent original indices found in chunk " << chunk_idx << " (Positions: " << chunk_original_indices[i] << ", " << chunk_original_indices[j] << ")" << std::endl; return false; } } } } // If no violations were found after checking all chunks, the permutation is valid. return true; } int main() { // --- Test Case 1: L=512, chunk_size=4 --- { const int L = 512; const int chunk_size = 4; Vec data(L / 64); // Vector size for 512 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); // Populate the data vector print_bits(data, L, "Original data (first 128 bits): "); try { Vec original_data_copy = data; // Keep a copy for verification permutation_mapping_fast(data, chunk_size, L); // Apply the optimized permutation print_bits(data, L, "Permuted data (first 128 bits): "); // Verify the result if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } // --- Test Case 2: L=1024, chunk_size=8 --- { const int L = 1024; const int chunk_size = 8; Vec data(L / 64); // Vector size for 1024 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); print_bits(data, L, "Original data (first 128 bits): "); try { Vec original_data_copy = data; permutation_mapping_fast(data, chunk_size, L); print_bits(data, L, "Permuted data (first 128 bits): "); if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } // --- Test Case 3: L=512, chunk_size=256 (Edge case L = 2 * chunk_size) --- { const int L = 512; const int chunk_size = 256; Vec data(L / 64); // Vector size for 512 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; get_bitstring(data, L); print_bits(data, L, "Original data (first 128 bits): "); try { Vec original_data_copy = data; permutation_mapping_fast(data, chunk_size, L); print_bits(data, L, "Permuted data (first 128 bits): "); if (verify_permutation(original_data_copy, chunk_size, L)) { std::cout << "Verification Result: PASSED" << std::endl; } else { std::cerr << "Verification Result: FAILED" << std::endl; } } catch (const std::exception& e) { std::cerr << "Error occurred: " << e.what() << std::endl; } std::cout << std::endl; } // Example of invalid input handling /* { const int L = 512; const int chunk_size = 5; // Not power of 2 Vec data(L / 64); std::cout << "--- Test Case: Invalid chunk_size ---" << std::endl; try { permutation_mapping_fast(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Caught expected exception: " << e.what() << std::endl; } std::cout << std::endl; } */ return 0; }This
permutation_mapping_fastfunction should give you a significant performance boost by reducing overhead and using optimized calculations. The primary remaining performance characteristic is dictated by the inherent data access pattern (scatter reads), which is difficult to overcome without specialized hardware instructions (SIMD scatter/gather).- Function Call Overhead: Calling
- User
Amazing! Now for verification of the results, I am looking for a reverse function as well, which does not need to be extremely fast. Could you provide me that one too?
Assistant
Okay, let's create a reverse mapping function. This function will take the permuted bit string and transform it back into the original bit string. It doesn't need the extreme optimization of the forward pass, but it should correctly undo the permutation.
The core idea is to find the inverse mapping: if the forward mapping takes an output position
iand tells us the original positionj = \sigma(i)where the bit came from, the inverse mapping takes an original positionjand tells us the output positioni = \sigma^{-1}(j)where that bit ended up.The reverse function will iterate through the original positions (
j) and, for eachj, calculate the corresponding permuted position (i) using the inverse mapping logic. It will then read the bit from the permuted data at positioniand place it into the correct positionjin a temporary buffer, which is then copied back.First, we need a helper function to compute the inverse mapping:
// --- Helper function to calculate the inverse mapping: sigma^{-1}(original_pos) = output_pos --- // Given an original position 'j' (0 to L-1), find the position 'i' in the permuted string // where the bit originally at 'j' now resides. // This function encapsulates the logic to find 'i' based on 'j'. inline int get_inverse_output_pos(int original_pos, int chunk_size, int L, int k_exponent, int B_exponent) { // chunk_size and L are validated before this function is called. // k_exponent = log2(chunk_size), B_exponent = log2(2 * chunk_size). int k = chunk_size; int B = 2 * k; // Block size (2 * chunk_size) // Masks for efficient bitwise operations (equivalent to modulo operations) int k_mask = k - 1; // mask = k - 1 int B_mask = B - 1; // mask = B - 1 // Calculate the block index 'b' and the position within that block 'pos_in_block'. // b = original_pos / (2k) => b = original_pos >> B_exponent int b = original_pos >> B_exponent; // pos_in_block = original_pos % (2k) => pos_in_block = original_pos & B_mask int pos_in_block = original_pos & B_mask; int output_pos; // This will be the calculated 'i' (position in the permuted string) // Determine which of the two sets within the block (even or odd indices) the 'original_pos' belongs to. // This is based on the parity of 'pos_in_block'. if ((pos_in_block & 1) == 0) { // If pos_in_block is even (0, 2, 4, ...), it belongs to G_{2b} // Set G_{2b} contains even indices within block 'b'. These sets map to even-indexed chunks C_{2b}. // The chunk index 'q' is therefore 2*b. int q = b << 1; // q = 2 * b // Calculate the offset 'r' within the set G_{2b}. // Elements of G_{2b} are {2bk, 2bk+2, ..., 2bk+2k-2}. The r-th element is 2bk + 2r. // We found 'pos_in_block' corresponds to 2r, so r = pos_in_block / 2. int r = pos_in_block >> 1; // The final output position 'i' is calculated as: i = q * k + r // Using bit shifts: i = (q << k_exponent) + r output_pos = (q << k_exponent) + r; } else { // If pos_in_block is odd (1, 3, 5, ...), it belongs to G_{2b+1} // Set G_{2b+1} contains odd indices within block 'b'. These sets map to odd-indexed chunks C_{2b+1}. // The chunk index 'q' is therefore 2*b + 1. int q = (b << 1) | 1; // q = 2 * b + 1 // Calculate the offset 'r' within the set G_{2b+1}. // Elements of G_{2b+1} are {2bk+1, 2bk+3, ..., 2bk+2k-1}. The r-th element is 2bk + 1 + 2r. // We found 'pos_in_block' corresponds to 1 + 2r, so 2r = pos_in_block - 1 => r = (pos_in_block - 1) / 2. int r = (pos_in_block - 1) >> 1; // The final output position 'i' is calculated as: i = q * k + r // Using bit shifts: i = (q << k_exponent) + r output_pos = (q << k_exponent) + r; } // Basic sanity check: Ensure the calculated output position is within the valid range [0, L-1]. if (output_pos < 0 || output_pos >= L) { // This indicates a logic error in the calculation or invalid input parameters passed. throw std::logic_error("get_inverse_output_pos: Calculated output_pos is out of bounds. Check logic or parameters."); } return output_pos; } /** * @brief Reverses the permutation mapping applied by permutation_mapping_fast. * * This function restores the bit string in 'data' (which should contain the permuted bits) * back to its original state before the permutation was applied. It achieves this by * calculating the source position in the permuted data for each target position in the * original data and transferring the bits accordingly. * * @param data The vector of uint64_t representing the permuted bit string. This vector will be modified in-place * to contain the original, unpermuted bit string. * @param chunk_size The chunk size used during the original permutation. Must be a power of 2 and >= 4. * @param L The total length of the bit string. Must be a power of 2. * * @throws std::invalid_argument if input parameters (chunk_size, L, data size) are invalid * or do not meet the requirements for the algorithm. */ void reverse_permutation_mapping(Vec& data, int chunk_size, int L) { // --- Input Validation (Identical to the forward function) --- // Ensure chunk_size is a power of 2 and at least 4. if (chunk_size <= 0 || (static_cast<uint64_t>(chunk_size) & (static_cast<uint64_t>(chunk_size) - 1)) != 0 || chunk_size < 4) { throw std::invalid_argument("reverse_permutation_mapping: chunk_size must be a power of 2 and >= 4."); } // Ensure L is a positive power of 2. if (L <= 0 || (static_cast<uint64_t>(L) & (static_cast<uint64_t>(L) - 1)) != 0) { throw std::invalid_argument("reverse_permutation_mapping: L must be a positive power of 2."); } // Ensure L is large enough for the chunk size. if (L < chunk_size) { throw std::invalid_argument("reverse_permutation_mapping: L must be greater than or equal to chunk_size."); } // The strategy requires that L is divisible by the block size (2 * chunk_size). int block_size = 2 * chunk_size; if (L % block_size != 0) { throw std::invalid_argument("reverse_permutation_mapping: L must be divisible by 2 * chunk_size for this strategy."); } // Verify that the provided vector 'data' correctly represents L bits. if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("reverse_permutation_mapping: The size of the 'data' vector does not correspond to L bits."); } // --- Precomputations for Efficiency --- // Calculate log2 values for chunk_size and block_size. These are used for fast division/modulo via bit shifts. int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(chunk_size)); int B_exponent = get_power_of_two_exponent(static_cast<uint64_t>(block_size)); size_t num_words = data.size(); // Create a temporary buffer to build the original (unpermuted) bit string. Initialize all bits to 0. Vec temp_buf(num_words, 0ULL); // --- Reverse Permutation Loop --- // Iterate through each bit position 'j' in the *original* bit string (from 0 to L-1). // For each 'j', we need to find where its bit came from in the permuted data. for (int j = 0; j < L; ++j) { // Calculate the position 'i' in the permuted string where the bit originally at 'j' is currently located. // This uses the inverse mapping logic. int i = get_inverse_output_pos(j, chunk_size, L, k_exponent, B_exponent); // --- Read the bit from the permuted data ('data' vector) at the calculated position 'i' --- // Determine the word index and the bit's position within that word for the permuted position 'i'. uint64_t word_idx_permuted = i / 64; int bit_idx_in_word_permuted = i % 64; // Extract the bit value. We only need to know if it's set (1) or not (0). // Using shift and bitwise AND is efficient. `1ULL` ensures the mask is 64-bit unsigned. bool bit_value = ((data[word_idx_permuted] >> bit_idx_in_word_permuted) & 1ULL); // --- Set the bit in the temporary buffer ('temp_buf') at the correct original position 'j' --- // If the extracted bit_value is true (meaning the bit was 1), set the corresponding bit in temp_buf. if (bit_value) { // Calculate the word index and bit index for the destination (original) position 'j'. uint64_t word_idx_orig = j / 64; int bit_idx_in_word_orig = j % 64; // Set the bit in the temporary buffer using bitwise OR. // `1ULL << bit_idx_in_word_orig` creates a mask with only the target bit set. temp_buf[word_idx_orig] |= (1ULL << bit_idx_in_word_orig); } // If bit_value is false (0), the bit in temp_buf remains 0 (as initialized), which is correct. } // --- Copy the reconstructed original data back to the input vector --- // After the loop, 'temp_buf' holds the original bit string. Copy it back into 'data'. std::copy(temp_buf.begin(), temp_buf.end(), data.begin()); }Explanation of the Reverse Function:
- Helper
get_inverse_output_pos: This function is the inverse of the forward mapping logic. Given anoriginal_pos(j), it calculates theoutput_pos(i) in the permuted string where that bit moved. It uses the same block-based partitioning strategy but works backward to find the source. - Input Validation: The validation checks are identical to the forward function to ensure consistency and correct application.
- Precomputations: Similar to the forward function,
log2values forchunk_sizeandblock_sizeare precomputed for efficient calculation using bit shifts. - Temporary Buffer: A
temp_bufis created to hold the reconstructed original data. This is necessary because we need to read from the permuted data while writing the restored data. - Reverse Permutation Loop:
- The loop iterates through each bit position
jfrom0toL-1. Thisjrepresents a position in the original bit string. - For each
j,get_inverse_output_posis called to findi, the position in the permuted string where the bit originally atjnow resides. - The bit at
data[i](the permuted data) is read. - If this bit is
1, the corresponding bit at positionjintemp_bufis set.
- The loop iterates through each bit position
- Final Copy: After the loop,
temp_bufcontains the fully restored original bit string.std::copytransfers this content back into the inputdatavector.
Example Usage and Verification
To properly test and verify this, we need the forward permutation function (
permutation_mapping_fast), helper functions for bit manipulation (get_bit,set_bit), a function to generate test data (get_bitstring), a way to print bits (print_bits), and a function to verify the constraint of the permutation itself.Here's the complete example
mainfunction, incorporating thereverse_permutation_mappingand a round-trip test:#include <vector> #include <cstdint> #include <numeric> // Not strictly needed but useful #include <algorithm> // For std::copy, std::min #include <stdexcept> // For exceptions #include <iostream> // For error reporting and testing output #include <cmath> // For std::abs in verification // Include headers for compiler intrinsics if needed for __builtin_ctz or _BitScanForward64 #if defined(_MSC_VER) #include <intrin.h> // For _BitScanForward64 #pragma intrinsic(_BitScanForward64) // Enable intrinsic #endif // Define Vec as requested using Vec = std::vector<uint64_t>; // --- Helper Function for log2 (using count trailing zeros) --- inline int get_power_of_two_exponent(uint64_t n) { #if defined(__GNUC__) || defined(__clang__) return __builtin_ctzll(n); #elif defined(_MSC_VER) unsigned long index; _BitScanForward64(&index, n); return static_cast<int>(index); #else int count = 0; while ((n & 1) == 0) { n >>= 1; count++; } return count; #endif } // --- Helper function to calculate the inverse mapping: sigma^{-1}(original_pos) = output_pos --- inline int get_inverse_output_pos(int original_pos, int chunk_size, int L, int k_exponent, int B_exponent) { int k = chunk_size; int B = 2 * k; int k_mask = k - 1; int B_mask = B - 1; int b = original_pos >> B_exponent; int pos_in_block = original_pos & B_mask; int output_pos; if ((pos_in_block & 1) == 0) { // Even pos_in_block -> G_{2b} -> chunk C_{2b} int q = b << 1; // q = 2 * b int r = pos_in_block >> 1; // r = pos_in_block / 2 output_pos = (q << k_exponent) + r; // i = q*k + r } else { // Odd pos_in_block -> G_{2b+1} -> chunk C_{2b+1} int q = (b << 1) | 1; // q = 2 * b + 1 int r = (pos_in_block - 1) >> 1; // r = (pos_in_block - 1) / 2 output_pos = (q << k_exponent) + r; // i = q*k + r } if (output_pos < 0 || output_pos >= L) { throw std::logic_error("get_inverse_output_pos: Calculated output_pos is out of bounds."); } return output_pos; } /** * @brief Reverses the permutation mapping applied by permutation_mapping_fast. * Restores the bit string in 'data' back to its original state. */ void reverse_permutation_mapping(Vec& data, int chunk_size, int L) { // Input Validation if (chunk_size <= 0 || (static_cast<uint64_t>(chunk_size) & (static_cast<uint64_t>(chunk_size) - 1)) != 0 || chunk_size < 4) { throw std::invalid_argument("reverse_permutation_mapping: chunk_size must be a power of 2 and >= 4."); } if (L <= 0 || (static_cast<uint64_t>(L) & (static_cast<uint64_t>(L) - 1)) != 0) { throw std::invalid_argument("reverse_permutation_mapping: L must be a positive power of 2."); } if (L < chunk_size) { throw std::invalid_argument("reverse_permutation_mapping: L must be greater than or equal to chunk_size."); } int block_size = 2 * chunk_size; if (L % block_size != 0) { throw std::invalid_argument("reverse_permutation_mapping: L must be divisible by 2 * chunk_size for this strategy."); } if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("reverse_permutation_mapping: The size of the 'data' vector does not correspond to L bits."); } // Precomputations int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(chunk_size)); int B_exponent = get_power_of_two_exponent(static_cast<uint64_t>(block_size)); size_t num_words = data.size(); Vec temp_buf(num_words, 0ULL); // Temporary buffer for the reconstructed original data. // Reverse Permutation Loop: Iterate through original positions 'j' for (int j = 0; j < L; ++j) { // Find where the bit originally at 'j' is located in the permuted data ('i'). int i = get_inverse_output_pos(j, chunk_size, L, k_exponent, B_exponent); // Read the bit from the permuted data ('data') at position 'i'. uint64_t word_idx_permuted = i / 64; int bit_idx_in_word_permuted = i % 64; bool bit_value = ((data[word_idx_permuted] >> bit_idx_in_word_permuted) & 1ULL); // Set the bit in the temporary buffer at the original position 'j'. if (bit_value) { uint64_t word_idx_orig = j / 64; int bit_idx_in_word_orig = j % 64; temp_buf[word_idx_orig] |= (1ULL << bit_idx_in_word_orig); } } // Copy the reconstructed original data back to the input vector. std::copy(temp_buf.begin(), temp_buf.end(), data.begin()); } // --- Forward Permutation Function (from previous response, needed for testing) --- /** * @brief Applies a permutation mapping to rearrange bits in a vector, optimized for speed. */ void permutation_mapping_fast(Vec& data, int chunk_size, int L) { // Input Validation if (chunk_size <= 0 || (static_cast<uint64_t>(chunk_size) & (static_cast<uint64_t>(chunk_size) - 1)) != 0 || chunk_size < 4) { throw std::invalid_argument("permutation_mapping_fast: chunk_size must be a power of 2 and >= 4."); } if (L <= 0 || (static_cast<uint64_t>(L) & (static_cast<uint64_t>(L) - 1)) != 0) { throw std::invalid_argument("permutation_mapping_fast: L must be a positive power of 2."); } if (L < chunk_size) { throw std::invalid_argument("permutation_mapping_fast: L must be greater than or equal to chunk_size."); } int block_size = 2 * chunk_size; if (L % block_size != 0) { throw std::invalid_argument("permutation_mapping_fast: L must be divisible by 2 * chunk_size for this strategy."); } if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("permutation_mapping_fast: The size of the 'data' vector does not correspond to L bits."); } // Precomputations int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(chunk_size)); int k_mask = chunk_size - 1; size_t num_words = data.size(); Vec temp_buf(num_words, 0ULL); // Optimized Permutation Loop for (size_t word_idx_dest = 0; word_idx_dest < num_words; ++word_idx_dest) { uint64_t current_dest_word = 0; int dest_word_start_bit = word_idx_dest * 64; for (int bit_offset = 0; bit_offset < 64; ++bit_offset) { int output_pos = dest_word_start_bit + bit_offset; // Calculate the original source position (`original_pos`) int q_val = output_pos >> k_exponent; int r_val = output_pos & k_mask; int original_pos; if ((q_val & 1) == 0) { // Even chunk index maps to even set G_{2b} int b = q_val >> 1; original_pos = (b * block_size) + (2 * r_val); } else { // Odd chunk index maps to odd set G_{2b+1} int b = q_val >> 1; original_pos = (b * block_size) + 1 + (2 * r_val); } // Read the bit from the source 'data' vector uint64_t word_idx_orig = original_pos / 64; int bit_idx_in_word_orig = original_pos % 64; bool source_bit_is_set = ((data[word_idx_orig] >> bit_idx_in_word_orig) & 1ULL); // Set the bit in the destination word accumulator if the source bit was 1 if (source_bit_is_set) { current_dest_word |= (1ULL << bit_offset); } } temp_buf[word_idx_dest] = current_dest_word; } std::copy(temp_buf.begin(), temp_buf.end(), data.begin()); } // --- Test Infrastructure --- // Helper to get a single bit (needed for verification and dummy get_bitstring) bool get_bit(const Vec& data, int bit_index) { size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("get_bit: bit_index is out of bounds."); } uint64_t word_index = bit_index / 64; int bit_index_in_word = bit_index % 64; return (data[word_index] >> bit_index_in_word) & 1; } // Helper to set a single bit (needed for dummy get_bitstring) void set_bit(Vec& data, int bit_index, bool value) { size_t total_bits = data.size() * 64; if (bit_index < 0 || static_cast<size_t>(bit_index) >= total_bits) { throw std::out_of_range("set_bit: bit_index is out of bounds."); } uint64_t word_index = bit_index / 64; int bit_index_in_word = bit_index % 64; if (value) { data[word_index] |= (1ULL << bit_index_in_word); } else { data[word_index] &= ~(1ULL << bit_index_in_word); } } // Placeholder function to simulate getting the bitstring data. void get_bitstring(Vec& data, int L) { if (static_cast<size_t>(L) != data.size() * 64) { throw std::invalid_argument("get_bitstring: Vector size mismatch with L."); } // Fill with a specific pattern for demonstration. // Example: Alternating 0s and 1s for the first 128 bits, then zeros. for (int i = 0; i < L; ++i) { if (i < 128) { set_bit(data, i, (i % 2) == 0); // Set bit to 1 if index is even } else { set_bit(data, i, false); // Rest are zeros } } } // Helper function for printing bits (useful for debugging/verification) void print_bits(const Vec& data, int L, const std::string& prefix = "") { std::cout << prefix; // Print a reasonable number of bits, e.g., first 128, for visualization int print_limit = std::min(L, 128); for (int i = 0; i < print_limit; ++i) { std::cout << get_bit(data, i); } if (L > print_limit) { std::cout << "..."; } std::cout << std::endl; } // Verification function: checks if the permutation logic itself satisfies the non-adjacent constraint. // This is done by calculating the original indices that would fall into each chunk. bool verify_permutation_constraint(int chunk_size, int L) { int k = chunk_size; int block_size = 2 * k; int num_chunks = L / k; // Precompute exponents for calculating original indices using bit shifts. int k_exponent = get_power_of_two_exponent(static_cast<uint64_t>(k)); int B_exponent = get_power_of_two_exponent(static_cast<uint64_t>(block_size)); // Check each chunk for the adjacency constraint. for (int chunk_idx = 0; chunk_idx < num_chunks; ++chunk_idx) { std::vector<int> chunk_original_indices; // Store original indices that feed into this chunk. for (int offset = 0; offset < k; ++offset) { int output_pos = chunk_idx * k + offset; // Current position in the permuted string's chunk. // Calculate the original position 'original_pos' that maps to this 'output_pos'. // This uses the forward mapping logic derived earlier. int q_val = output_pos >> k_exponent; // Chunk index (q) int r_val = output_pos & (k - 1); // Offset within chunk (r) int original_pos; if ((q_val & 1) == 0) { // Even chunk index 'q' maps to even original index set G_{2b} int b = q_val >> 1; // Block index 'b' original_pos = (b * block_size) + (2 * r_val); // original_pos = b*(2k) + 2r } else { // Odd chunk index 'q' maps to odd original index set G_{2b+1} int b = q_val >> 1; // Block index 'b' original_pos = (b * block_size) + 1 + (2 * r_val); // original_pos = b*(2k) + 1 + 2r } chunk_original_indices.push_back(original_pos); } // Check all pairs of original indices within this chunk for adjacency. for (size_t i = 0; i < chunk_original_indices.size(); ++i) { for (size_t j = i + 1; j < chunk_original_indices.size(); ++j) { if (std::abs(chunk_original_indices[i] - chunk_original_indices[j]) == 1) { // Found adjacent original indices within the same chunk. Constraint violated. std::cerr << "Constraint Verification Failed: Adjacent original indices found in chunk " << chunk_idx << " (Positions: " << chunk_original_indices[i] << ", " << chunk_original_indices[j] << ")" << std::endl; return false; // Indicate failure } } } } // If no violations were found after checking all chunks, the permutation logic itself is correct. return true; } int main() { // --- Test Case 1: L=512, chunk_size=4 --- { const int L = 512; const int chunk_size = 4; Vec data(L / 64); // Vector size for 512 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; // 1. Verify the permutation logic itself first (does it satisfy the constraint?) if (!verify_permutation_constraint(chunk_size, L)) { std::cerr << "Constraint verification FAILED for initial parameters. Aborting test." << std::endl; return 1; // Exit if the fundamental logic is flawed. } else { std::cout << "Constraint verification PASSED." << std::endl; } // 2. Prepare data get_bitstring(data, L); // Populate the data vector with a test pattern print_bits(data, L, "Original data (first 128 bits): "); Vec original_data_copy = data; // Keep a copy of the original data for final comparison. // 3. Apply the forward permutation try { permutation_mapping_fast(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during forward permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Permuted data (first 128 bits): "); // 4. Apply the reverse permutation try { reverse_permutation_mapping(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during reverse permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Data after reverse perm. (first 128 bits): "); // 5. Verify that the data is restored correctly (round-trip test) if (data == original_data_copy) { std::cout << "Round-trip verification: PASSED (Original data restored correctly)" << std::endl; } else { std::cerr << "Round-trip verification: FAILED (Data mismatch after reverse permutation)" << std::endl; } std::cout << std::endl; } // --- Test Case 2: L=1024, chunk_size=8 --- { const int L = 1024; const int chunk_size = 8; Vec data(L / 64); // Vector size for 1024 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; if (!verify_permutation_constraint(chunk_size, L)) { std::cerr << "Constraint verification FAILED for initial parameters. Aborting test." << std::endl; return 1; } else { std::cout << "Constraint verification PASSED." << std::endl; } get_bitstring(data, L); print_bits(data, L, "Original data (first 128 bits): "); Vec original_data_copy = data; try { permutation_mapping_fast(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during forward permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Permuted data (first 128 bits): "); try { reverse_permutation_mapping(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during reverse permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Data after reverse perm. (first 128 bits): "); if (data == original_data_copy) { std::cout << "Round-trip verification: PASSED" << std::endl; } else { std::cerr << "Round-trip verification: FAILED" << std::endl; } std::cout << std::endl; } // --- Test Case 3: L=512, chunk_size=256 (Edge case L = 2 * chunk_size) --- { const int L = 512; const int chunk_size = 256; Vec data(L / 64); // Vector size for 512 bits std::cout << "--- Test Case: L=" << L << ", chunk_size=" << chunk_size << " ---" << std::endl; if (!verify_permutation_constraint(chunk_size, L)) { std::cerr << "Constraint verification FAILED for initial parameters. Aborting test." << std::endl; return 1; } else { std::cout << "Constraint verification PASSED." << std::endl; } get_bitstring(data, L); print_bits(data, L, "Original data (first 128 bits): "); Vec original_data_copy = data; try { permutation_mapping_fast(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during forward permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Permuted data (first 128 bits): "); try { reverse_permutation_mapping(data, chunk_size, L); } catch (const std::exception& e) { std::cerr << "Error during reverse permutation: " << e.what() << std::endl; return 1; } print_bits(data, L, "Data after reverse perm. (first 128 bits): "); if (data == original_data_copy) { std::cout << "Round-trip verification: PASSED" << std::endl; } else { std::cerr << "Round-trip verification: FAILED" << std::endl; } std::cout << std::endl; } return 0; }- Helper
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.