[問題] uint32陣列每筆資料多一個bit當flag轉換

作者: s6414073   2024-04-15 18:46:08
開發平台(Platform): (Ex: Win10, Linux, ...)
Linux
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
gcc
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)

問題(Question):
在每一筆數據的第31bit加入flag,0表示後面還有元素,1表示後面沒有元素,
也就是最後一筆元素;
每一筆的0-30bit為數據,第31bit原本的資料會放到第二筆數據的bit0,
原本第二筆的數據0~29bit要做right shift
也就是原來第一筆數據的bit31跑到第二筆數據的的bit0,
原本第二筆數據的0-29bit變成1-30bit,第二筆的bit31仍為flag,
要設計出n個元素都能通用的函數
餵入的資料(Input):
unsigned int input_data[3] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
預期的正確結果(Expected Output):
unsigned int output_data[4] = {0x7FFFFFFF,0x7FFFFFFF,0x7FFFFFFF,0x80000007};
錯誤結果(Wrong Output):
最後一筆應為0x80000007
實際上跑出來是0x80000000
程式碼(Code):(請善用置底文網頁, 記得排版,禁止使用圖檔)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
// Define the flag bit value
#define FLAG_BIT 0x80000000
// Function to convert array of unsigned integers
unsigned int* convert_data(unsigned int* input_data, int len) {
// Allocate memory for the output data
unsigned int* output_data = (unsigned int*)malloc((len + 1) *
sizeof(unsigned int));
if (output_data == NULL) {
perror("Failed to allocate memory");
exit(EXIT_FAILURE);
}
// Convert each element
for (int i = 0; i < len; i++) {
// Extract the data part (lower 31 bits) of the current input element
unsigned int data = input_data[i] & 0x7FFFFFFF;
// Extract the flag bit of the current input element
unsigned int flag = (input_data[i] >> 31) & 0x1;
// Combine data and flag to form the output element
output_data[i] = data;
// Set the flag bit of the next element if this is not the last
element
if (i < len - 1) {
output_data[i + 1] = (flag << 31) | (output_data[i + 1] >> 1);
}
}
// Set the flag bit of the last element to indicate the end
output_data[len] = FLAG_BIT | (output_data[len] >> 1);
return output_data;
}
int main() {
unsigned int input_data[3] = {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF};
int len = sizeof(input_data) / sizeof(input_data[0]);
// Convert the data
unsigned int* output_data = convert_data(input_data, len);
// Print the converted data
for (int i = 0; i < len + 1; i++) {
printf("output_data[%d] = 0x%08X\n", i, output_data[i]);
}
// Free the allocated memory
free(output_data);
return 0;
}
補充說明(Supplement):
或是有沒有現成的library可以做這件事?
作者: wulouise (在線上!=在電腦前)   2024-04-15 19:27:00
不懂為什麼要這樣設計,header直接給長度不是更簡單?而且你的程式根本沒考慮到input的carry over吧..
作者: stupid0319 (徵女友)   2024-04-15 20:41:00
這麼簡單,還要找library?
作者: ssdoz2sk (眷戀著提拉米蘇的風采~)   2024-04-16 02:31:00
輸出的長度應該為(len*32+30)/31,再來carry的長度會因為你縮減儲存空間越來越長,i=1 carry 1bit,i=2 carry2bit,直到 31bytes data 擴展成 32bytes。你 code 考慮的 carry 長度不應該是固定的,況且你在 i++ 後又用 input 的 bit 0-31 蓋掉是在??
作者: johnjohnlin (嗯?)   2024-04-16 07:41:00
c bit field是你要的嗎
作者: akasan (KITO)   2024-04-16 23:50:00
leb128
作者: Qbsuran (Qbsuran)   2024-05-16 00:32:00
類似作法在nginx有做到 他是利用malloc/calloc的最後一個bit一定會對齊偶數, 所以就可以利用最後一個bit做flagnginx自己實作的memory pool也是會對齊偶數nginx實作在這 https://reurl.cc/6vvDb6
作者: Lipraxde (Lipraxde)   2024-05-16 22:40:00
這種 tricky 的玩法在真的很計較空間的時候再用就好了啦,沒事用這招瞎搞,秀完技巧後剩下的就是麻煩

Links booklink

Contact Us: admin [ a t ] ucptt.com