Try   HackMD

2020q1 Homework3 (quiz4)

contributed by < StevenChen8759 >

tags: linux2020

quiz4 題目說明

:Camera: 測驗一 - bitcpy

:camera_with_flash: 運作原理與填答

  • 觀察下列函式 bitcpy 的操作,可發現在寫入位址的操作計算上採用了位元運算。
size_t read_lhs = _read & 7; // Perform _read mod 8 in bitwise operation size_t read_rhs = 8 - read_lhs; // Get bit position offset in a uint8_t space const uint8_t *source = _src + (_read / 8); // Offset to assigned array position for reading src size_t write_lhs = _write & KK1; // Perform _write mod 8 in bitwise operation size_t write_rhs = 8 - write_lhs; // Get bit position offset in a uint8_t space uint8_t *dest = _dest + (_write / 8); // Offset to assigned array position for writing dest
  • 函式 bitcpy 會將 source 之第0個位元算起偏移 _read 個位元,複製 _count 個位元到dest 之第0個位元算起偏移 _write 個位元
  • 因為儲存位元的資料型態為 uint8_t ,每一個陣列欄位為 8 bits ,因此在陣列元素的欄位偏移_write 值除以 8,而陣列元素內的位元偏移則為 _write 取餘數8,其操作等價於取 _write 的最低 3 位元,故填答 KK1 之值為 7。
#define KK1 7
  • 我們接著分析實作位元複製的迴圈,其程式碼實現如下:
/* Copy all bits in number _count */ while (_count > 0) { // Read data from source and move to next position data = *source++; bitsize = (_count > 8) ? 8 : _count; // Set Operating bit size // Bit offset in uint8_t space is not zero if (read_lhs > 0) { data <<= read_lhs; // Align to position zero if (bitsize > read_rhs) // If tailed reading bits in the next position of array data |= (*source >> read_rhs); // Concate these bit into current position of array } // Reading bit size is smaller than 8, mask bits which are not necessary if (bitsize < 8) data &= read_mask[bitsize]; // Assign data before writing to variable original original = *dest; // Bit offset in uint8_t space is not zero if (write_lhs > 0) { // Assign read mask for leading 0~8 bits mask = read_mask[write_lhs]; // Writing bits is crossing two elements in array if (bitsize > write_rhs) { // Mask bits in front of start position, and write available bits started from offset *dest++ = (original & mask) | (data >> write_lhs); // Write bits which cannot write into previous position original = *dest & write_mask[bitsize - write_rhs]; // Move written bits to correct position *dest = original | (data << write_rhs); } else { // For writing position is not started from zero case, adjust mask for writing bits if ((bitsize - write_lhs) > 0) mask = mask | write_mask[8 - (bitsize - write_lhs)]; // Assign data with mask and concate data if necessary *dest++ = (original & mask) | (data >> write_lhs); } } else { // Mask data output while uint8_t is not fully written if (bitsize < 8) data = data | (original & write_mask[bitsize]); // Data assignment *dest++ = data; } _count -= KK2; // Write bitsize bits for each iteration, minus bitsize }

:camera_with_flash: 原始程式碼效能改善

:camera_with_flash: 考慮 Alignment 以及 Word Size 之效能改善

:camera_with_flash: Linux 原始碼中的運用 bitcpy 技巧的場合

:camera: 測驗二 - Vector

:camera_with_flash: 運作原理與填答

:camera_with_flash: 程式效率分析

:camera_with_flash: 實作上限制與改善方案

:camera_with_flash: 基於上述程式實現 folly::fbvector 中的經典操作