linux2020
目的: 檢驗學員對 bitwise 操作, 指標操作, 前置處理器應用 的認知
1
考慮到以下 bitcpy
實作,允許開發者對指定的記憶體區域,逐 bit 進行資料複製:
#include <stdint.h>
#include <stdio.h>
#include <string.h>
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t _count)
{
uint8_t data, original, mask;
size_t bitsize;
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = _src + (_read / 8);
size_t write_lhs = _write & KK1;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = _dest + (_write / 8);
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
while (_count > 0) {
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
original = *dest;
if (write_lhs > 0) {
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
if ((bitsize - write_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
} else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
_count -= KK2;
}
}
對應的測試程式碼:
static uint8_t output[8], input[8];
static inline void dump_8bits(uint8_t _data)
{
for (int i = 0; i < 8; ++i)
printf("%d", (_data & (0x80 >> i)) ? 1 : 0);
}
static inline void dump_binary(uint8_t *_buffer, size_t _length)
{
for (int i = 0; i < _length; ++i)
dump_8bits(*_buffer++);
}
int main(int _argc, char **_argv)
{
memset(&input[0], 0xFF, sizeof(input));
for (int i = 1; i <= 32; ++i) {
for (int j = 0; j < 16; ++j) {
for (int k = 0; k < 16; ++k) {
memset(&output[0], 0x00, sizeof(output));
printf("%2d:%2d:%2d ", i, k, j);
bitcpy(&output[0], k, &input[0], j, i);
dump_binary(&output[0], 8);
printf("\n");
}
}
}
return 0;
}
測試程式碼的參考輸出:
1: 0: 0 1000000000000000000000000000000000000000000000000000000000000000
1: 1: 0 0100000000000000000000000000000000000000000000000000000000000000
1: 2: 0 0010000000000000000000000000000000000000000000000000000000000000
...
1:15: 0 0000000000000001000000000000000000000000000000000000000000000000
1: 0: 1 1000000000000000000000000000000000000000000000000000000000000000
1: 1: 1 0100000000000000000000000000000000000000000000000000000000000000
1: 2: 1 0010000000000000000000000000000000000000000000000000000000000000
...
1:15: 1 0000000000000001000000000000000000000000000000000000000000000000
...
請補完程式碼。
作答區
KK1 = ?
(a)
1(b)
2(c)
3(d)
4(e)
5(f)
6(g)
7(h)
8KK2 = ?
(a)
1(b)
-1(c)
0xFF(d)
bitsize(e)
write_rhs(f)
write_lhs延伸問題:
提示: 觀察 linux/bitops.h 裡頭巨集在原始程式碼的運用狀況
2
考慮到一個針對空間處理最佳化的 vector 實作
支援以下操作:
vec_push_back
: 新增元素至 vector 的尾端,必要時會進行記憶體配置;vec_pop_back()
: 刪除 vector 最尾端的元素;每個 vector 都有兩個重要的屬性:
使用示範:
int main()
{
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
vec_pos(vec2, 1));
vec_push_back(vec2, 88);
vec_reserve(vec2, 100);
printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
vec_capacity(vec2));
printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));
#define display(v) \
do { \
for (size_t i = 0; i < vec_size(v); i++) \
printf("%.2f ", vec_pos(v, i)); \
puts(v.on_heap ? "heap" : "stack"); \
} while (0)
display(vec1);
vec_push_back(vec1, 0.0);
display(vec1);
vec_push_back(vec1, 1.1);
display(vec1);
vec_push_back(vec1, 2.2);
display(vec1);
vec_push_back(vec1, 3.3);
display(vec1);
vec_push_back(vec1, 4.4);
display(vec1);
vec_push_back(vec1, 5.5);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
vec_pop_back(vec1);
display(vec1);
return 0;
}
預期輸出:
pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap
本體的實作程式如下:
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* vector with small buffer optimization */
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
#define NEXT_POWER_OF_2(s) \
VV1 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
#define v(t, s, name, ...) \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - 1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
#define vec_size(v) v.size
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
#define vec_pop_back(v) (void) (VV2)
/* This function attribute specifies function parameters that are not supposed
* to be null pointers. This enables the compiler to generate a warning on
* encountering such a parameter.
*/
#define NON_NULL __attribute__((nonnull))
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
請補完程式碼。
參閱 你所不知道的C語言:技巧篇 以得知 GCC extension: attribute cleanup 使用技巧。
作答區
VV1 =
(a)
s(b)
s - 1(c)
s & (s - 1)(d)
(s & (s - 1)) == 0VV2 =
(a)
v.size -= 1
(b)
v.capacity--
延伸問題:
回歸第一手資料,透過反思 C 語言程式設計的細節,重新學習電腦原理
Jul 21, 2025自 Linux 核心原始程式碼編譯出 User-mode Linux 並運用工具來建構實驗所需的檔案系統
Jul 20, 2025系統的 throughput 是評斷排程器優劣的重要效能
Jul 19, 2025無論是作業系統核心、C 語言函式庫內部、程式開發框架,到應用程式,都不難見到 linked list 的身影,包含多種針對效能和安全議題所做的 linked list 變形,又還要考慮到應用程式的泛用性 (generic programming),是很好的進階題材。
Jul 17, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up