Tìm vị trí của '1 hiệu quả trong một mảng bit

Question

Tôi đang nối dây chương trình kiểm tra một bộ dây cho mạch hở hoặc ngắn. Chương trình, chạy trên một AVR, điều khiển một vector thử nghiệm (đi bộ '1') lên dây và nhận kết quả trở lại. Nó so sánh vector kết quả này với dữ liệu dự kiến ​​đã được lưu trữ trên thẻ SD hoặc EEPROM bên ngoài.

Đây là một ví dụ, giả sử chúng ta có một bộ gồm 8 dây, tất cả đều thẳng qua tức là chúng không có nút giao. Vì vậy, nếu chúng ta lái xe 0b00000010 chúng ta sẽ nhận được 0b00000010.

Giả sử chúng tôi nhận 0b11000010. Điều này ngụ ý có một mạch ngắn giữa dây 7,8 và dây 2. Tôi có thể phát hiện các bit mà tôi quan tâm bằng 0b00000010^0b11000010 = 0b11000000. Điều này cho tôi biết rõ ràng dây 7 và 8 có lỗi nhưng làm thế nào để tôi tìm được vị trí của những '1 hiệu quả trong một mảng bit lớn. Thật dễ dàng để làm điều này cho chỉ 8 dây sử dụng mặt nạ bit nhưng hệ thống tôi đang phát triển phải xử lý lên đến 300 dây (bit). Trước khi tôi bắt đầu sử dụng các macro như sau và kiểm tra từng bit trong một mảng 300 * 300-bit, tôi muốn hỏi ở đây nếu có một giải pháp thanh lịch hơn.

#define BITMASK(b) (1 << ((b) % 8)) 
#define BITSLOT(b) ((b/8)) 
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b)) 
#define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b)) 
#define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b)) 
#define BITNSLOTS(nb) ((nb + 8 - 1)/8) 

Chỉ để tiếp tục cho biết cách phát hiện mạch mở. Dữ liệu dự kiến: 0b00000010, dữ liệu nhận được: 0b00000000 (dây không được kéo cao). 0b00000010^0b00000000 = 0b0b00000010 - dây 2 đang mở.

LƯU Ý: Tôi biết thử nghiệm 300 dây không phải là một cái gì đó RAM nhỏ bên trong một AVR Mega 1281 có thể xử lý, đó là lý do tại sao tôi sẽ chia này thành các nhóm, nghĩa là kiểm tra 50 dây, so sánh, kết quả hiển thị và sau đó di chuyển về phía trước.

Answer 1

Nhiều kiến ​​trúc cung cấp hướng dẫn cụ thể để định vị bit thiết lập đầu tiên trong một từ hoặc để đếm số bit đã đặt. Các trình biên dịch thường cung cấp nội tại cho các hoạt động này, do đó bạn không phải viết assembly nội tuyến. GCC, ví dụ, cung cấp __builtin_ffs, __builtin_ctz, __builtin_popcount, v.v., mỗi trong số đó sẽ ánh xạ tới lệnh thích hợp trên kiến ​​trúc đích, khai thác song song mức bit.

Nếu kiến ​​trúc đích không hỗ trợ chúng, việc triển khai phần mềm hiệu quả sẽ được trình biên dịch phát ra. Cách tiếp cận ngây thơ của việc kiểm tra bit bit bằng bit trong phần mềm không hiệu quả lắm.

Nếu trình biên dịch của bạn không triển khai các tính năng này, bạn vẫn có thể mã thực hiện của riêng mình bằng cách sử dụng de Bruijn sequence.

Answer 2

Bạn có thể sử dụng bảng tra cứu. Ví dụ log-base-2 tra cứu bảng của 255 byte có thể được sử dụng để tìm ra nhiều nhất có ý nghĩa 1-bit trong một byte:

uint8_t bit1 = log2[bit_mask]; 

nơi log2 được định nghĩa như sau:

uint8_t const log2[] = { 
    0,    /* not used log2[0] */ 
    0,    /* log2[0x01] */ 
    1, 1    /* log2[0x02], log2[0x03] */ 
    2, 2, 2, 2,  /* log2[0x04],..,log2[0x07] */ 
    3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ 
    ... 
} 

On hầu hết các bộ vi xử lý một bảng tra cứu như thế này sẽ đi đến ROM. Nhưng AVR là một máy Harvard và để đặt dữ liệu trong không gian mã (ROM) đòi hỏi phần mở rộng không chuẩn đặc biệt, phụ thuộc vào trình biên dịch. Ví dụ trình biên dịch IAR AVR sẽ cần sử dụng từ khóa mở rộng __flash. Trong WinAVR (GNU AVR), bạn sẽ cần phải sử dụng thuộc tính PROGMEM, nhưng nó phức tạp hơn thế, bởi vì bạn cũng sẽ cần phải sử dụng các macro đặc biệt để đọc từ không gian chương trình.

Answer 3

Tần suất bạn mong đợi lỗi? Nếu bạn không mong đợi họ thường xuyên, sau đó nó có vẻ vô nghĩa để tối ưu hóa "lỗi tồn tại" trường hợp - phần duy nhất mà thực sự sẽ quan trọng cho tốc độ là "không có lỗi" trường hợp.

Để tối ưu hóa trường hợp không có lỗi, chỉ cần XOR kết quả thực tế với kết quả mong đợi và kiểm tra input^expected == 0 để xem có bất kỳ bit nào được đặt hay không.

Bạn có thể sử dụng chiến lược tương tự để tối ưu hóa trường hợp "vài lỗi", nếu bạn mong đợi số lượng lỗi thường nhỏ hơn khi chúng tồn tại - hãy đặt giá trị input^expected để nhận 8 bit đầu tiên, 8 bit thứ hai, v.v. và so sánh từng kết quả với 0. Sau đó, bạn chỉ cần tìm kiếm các bit thiết lập trong các bit không bằng không, điều này sẽ thu hẹp không gian tìm kiếm thành một thứ có thể được thực hiện khá nhanh chóng.

Answer 4

Tôi nghĩ rằng chỉ có một cách để làm điều này:

• Tạo một mảng out "outdata". Mỗi mục của mảng có thể tương ứng với một thanh ghi cổng 8 bit.
• Gửi dữ liệu ngoài trên dây.
• Đọc lại dữ liệu này dưới dạng "indata".
• Lưu trữ indata trong một mảng được ánh xạ chính xác như dữ liệu ngoài.
• Trong một vòng lặp, XOR mỗi byte của outdata với mỗi byte của indata.

---

Tôi rất muốn giới thiệu các hàm nội tuyến thay vì các macro đó.

Tại sao MCU không thể xử lý 300 dây?

300/8 = 37,5 byte. Làm tròn đến 38. Nó cần phải được lưu trữ hai lần, outdata và indata, 38 * 2 = 76 byte.

Bạn không thể sử dụng 76 byte RAM?

Answer 5

Tôi nghĩ rằng bạn đang thiếu rừng thông qua các cây. Có vẻ như là một chiếc giường kiểm tra móng tay. Trước tiên hãy kiểm tra một số giả định: 1) Bạn biết chân nào nên được sống cho từng pin được thử nghiệm/được cấp nguồn. 2) bạn có một danh sách net được dịch cho bước 1 thành tệp trên sd

Nếu bạn hoạt động ở mức byte cũng như bit, nó sẽ đơn giản hóa vấn đề. Nếu bạn tiếp thêm sinh lực cho một ghim, có một mẫu dự kiến ​​được lưu trữ trong tệp của bạn. Đầu tiên tìm các byte không khớp; xác định các chân không khớp trong byte; cuối cùng lưu trữ pin năng lượng với số pin bị lỗi.

Bạn không cần mảng để tìm kiếm hoặc kết quả. ý tưởng chung:

numwires=300; 

numbytes=numwires/8 + (numwires%8)?1:0; 

for(unsigned char currbyte=0; currbyte<numbytes; currbyte++) 
{ 
    unsigned char testbyte=inchar(baseaddr+currbyte) 
    unsigned char goodbyte=getgoodbyte(testpin,currbyte/*byte offset*/); 
    if(testbyte^goodbyte){ 
    // have a mismatch report the pins 
    for(j=0, mask=0x01; mask<0x80;mask<<=1, j++){ 
     if((mask & testbyte) != (mask & goodbyte)) // for clarity 
      logbadpin(testpin, currbyte*8+j/*pin/wirevalue*/, mask & testbyte /*bad value*/); 

    } 

}