असाइन किए गए बिट सरणी की प्रतिलिपि बनाने के लिए एक समय कुशल एल्गोरिदम क्या है?

Question

मुझे अतीत में कई बार ऐसा करना पड़ा, और मैं कभी भी परिणामों से संतुष्ट नहीं हुआ।

क्या कोई भी स्रोत से गंतव्य तक एक संगत बिट सरणी की प्रतिलिपि बनाने का एक तेज़ तरीका सुझा सकता है, जहां सुविधाजनक प्रोसेसर सीमाओं पर स्रोत और गंतव्य दोनों को गठबंधन नहीं किया जा सकता है (दाएं स्थानांतरित)?

यदि स्रोत और गंतव्य दोनों को गठबंधन नहीं किया गया है, तो समस्या को जल्दी से बदला जा सकता है जहां उनमें से केवल एक को गठबंधन नहीं किया जाता है (पहली प्रतिलिपि के बाद)।

एक प्रारंभिक बिंदु के रूप में, मेरी कोड अनिवार्य रूप से (यह सिर्फ एक कफ उदाहरण बंद है अपरीक्षित, उपेक्षा साइड इफेक्ट) निम्नलिखित की तरह कुछ के लिए देख समाप्त होता है:

const char mask[8] = { 1, 3, 7, 15, 31, 63, 127, 255 }; 
/* Assume: 
* - destination is already zeroed, 
* - offsets are right shifts 
* - bits to copy is big (> 32 say) 
*/ 
int bitarray_copy(char * src, int src_bit_offset, int src_bit_len, 
        char * dst, int dst_bit_offset) { 
    if (src_bit_offset == dst_bit_offset) { /* Not very interesting */ 
    } else { 
     int bit_diff_offset = src_bit_offset - dst_bit_offset; /* assume positive */ 
     int loop_count; 
     char c; 
     char mask_val = mask[bit_diff_offset]; 

     /* Get started, line up the destination. */ 
     c = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val); 
     c &= mask[8-dst_bit_offset]; 

     *dst++ |= c; 

     src_bit_len -= 8 - dst_bit_offset; 
     loop_count = src_bit_len >> 3; 

     while (--loop_count >= 0) 
      * dst ++ = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val); 

     /* Trailing tail copy etc ... */ 
     if (src_bit_len % 8) /* ... */ 
    } 
} 

(वास्तव में इस से बेहतर मैं है पहले किया है। यह बहुत बुरा नहीं लग रहा है)

Answer 1

आपका आंतरिक पाश दो बाइट्स के टुकड़े लेता है और उन्हें एक गंतव्य बाइट में ले जाता है। यह लगभग इष्टतम है। यहां किसी विशेष क्रम में कुछ और संकेत दिए गए हैं:

• एक समय में बाइट को सीमित करने की आवश्यकता नहीं है। सबसे बड़ा पूर्णांक आकार का उपयोग करें जो आपका मंच आपको दूर जाने देगा। यह निश्चित रूप से आपके शुरुआती और पिछला तर्क जटिल करेगा।
• यदि आप बिना हस्ताक्षर किए गए वर्ण या पूर्णांक का उपयोग करते हैं, तो आपको सही स्थानांतरित होने के बाद स्रोत के दूसरे भाग को मुखौटा करने की आवश्यकता नहीं हो सकती है। यह आपके कंपाइलर पर निर्भर करेगा।
• यदि आपको मास्क की आवश्यकता है, तो सुनिश्चित करें कि आपका कंपाइलर लूप के बाहर टेबल लुकअप को ले जा रहा है। यदि ऐसा नहीं है, तो इसे एक अस्थायी चर में कॉपी करें और इसका उपयोग करें।

Answer 2

आपका समाधान सबसे अधिक देखा गया है जैसा कि मैंने देखा है: मूल रूप से गठबंधन पहुंच का उपयोग करके बीच में मुख्य पाश के साथ शुरुआत और अंत में कुछ असाइन किए गए काम करते हैं। यदि आपको वास्तव में दक्षता की आवश्यकता है और इसे बहुत लंबे समय तक चलाना है, तो मैं मुख्य लूप में एसएसई 2 जैसी कुछ आर्किटेक्चर-विशिष्ट का उपयोग करने का सुझाव दूंगा।

Answer 3

लक्ष्य प्लेटफॉर्म पर इष्टतम निर्भरता क्या होगी। बैरल शिफ्टर्स के बिना कुछ प्लेटफार्मों पर, पूरे वेक्टर को दाएं या बाएं, एक बार, एन < 3 के लिए स्थानांतरित करना, सबसे तेज़ दृष्टिकोण होगा (पीआईसी 18 प्लेटफ़ॉर्म पर, एक 8x-अनियंत्रित बाइट लूप को बाएं एक बिट को स्थानांतरित करने के लिए 11 खर्च होंगे आठ बाइट प्रति निर्देश चक्र)।

 
    src1 = *src++; 
    src2 = (src1 shl shiftamount1) | (src2 shr shiftamount2); 
    *dest++ = src2; 
    src2 = *src++; 
    src1 = (src2 shl shiftamount1) | (src1 shr shiftamount2); 
    *dest++ = src1; 

अन्यथा, मुझे पसंद है पैटर्न (टिप्पणी src2 आप अपने बफर के अंत के साथ क्या किया चाहते हैं पर निर्भर करता है प्रारंभ करना होगा) खुद को बहुत ही कुशल कार्यान्वयन उधार देने चाहिए एक हाथ पर (आठ निर्देश हर दो शब्द, यदि पंजीयक src, dest, src1, src2, shiftamount1, और shiftamount2 के लिए उपलब्ध हैं। अधिक रजिस्टरों का उपयोग करने से बहु-शब्द लोड/स्टोर निर्देशों के माध्यम से तेज़ी से संचालन की अनुमति मिल जाएगी। चार शब्द हैंडलिंग कुछ ऐसा होगा (प्रति पंक्ति एक मशीन निर्देश, पहली चार पंक्तियों को छोड़कर एक साथ एक निर्देश होगा, जैसा कि पिछली चार पंक्तियां होगी):

 
    src0 = *src++; 
    src1 = *src++; 
    src2 = *src++; 
    src3 = *src++; 
    tmp = src0; 
    src0 = src0 shr shiftamount1 
    src0 = src0 | src1 shl shiftamount2 
    src1 = src1 shr shiftamount1 
    src1 = src1 | src2 shl shiftamount2 
    src2 = src2 shr shiftamount1 
    src2 = src2 | src3 shl shiftamount2 
    src3 = src3 shr shiftamount1 
    src3 = src3 | tmp shl shiftamount2 
    *dest++ = src0; 
    *dest++ = src1; 
    *dest++ = src2; 
    *dest++ = src3; 

प्रति 16 बाइट प्रति ग्यारह निर्देश घुमाए गए।

Answer 4

यही वह है जो मैंने किया। (EDIT एक बिट बिट कॉपी बग के लिए 8/21/2014 को बदल दिया गया।)

#include <limits.h> 
#include <string.h> 
#include <stddef.h> 

#define PREPARE_FIRST_COPY()          \ 
    do {               \ 
    if (src_len >= (CHAR_BIT - dst_offset_modulo)) {    \ 
     *dst  &= reverse_mask[dst_offset_modulo];    \ 
     src_len -= CHAR_BIT - dst_offset_modulo;     \ 
    } else {              \ 
     *dst  &= reverse_mask[dst_offset_modulo]    \ 
       | reverse_mask_xor[dst_offset_modulo + src_len]; \ 
     c  &= reverse_mask[dst_offset_modulo + src_len]; \ 
     src_len = 0;            \ 
    } } while (0) 


static void 
bitarray_copy(const unsigned char *src_org, int src_offset, int src_len, 
        unsigned char *dst_org, int dst_offset) 
{ 
    static const unsigned char mask[] = 
     { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff }; 
    static const unsigned char reverse_mask[] = 
     { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff }; 
    static const unsigned char reverse_mask_xor[] = 
     { 0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00 }; 

    if (src_len) { 
     const unsigned char *src; 
       unsigned char *dst; 
     int     src_offset_modulo, 
          dst_offset_modulo; 

     src = src_org + (src_offset/CHAR_BIT); 
     dst = dst_org + (dst_offset/CHAR_BIT); 

     src_offset_modulo = src_offset % CHAR_BIT; 
     dst_offset_modulo = dst_offset % CHAR_BIT; 

     if (src_offset_modulo == dst_offset_modulo) { 
      int    byte_len; 
      int    src_len_modulo; 
      if (src_offset_modulo) { 
       unsigned char c; 

       c = reverse_mask_xor[dst_offset_modulo]  & *src++; 

       PREPARE_FIRST_COPY(); 
       *dst++ |= c; 
      } 

      byte_len = src_len/CHAR_BIT; 
      src_len_modulo = src_len % CHAR_BIT; 

      if (byte_len) { 
       memcpy(dst, src, byte_len); 
       src += byte_len; 
       dst += byte_len; 
      } 
      if (src_len_modulo) { 
       *dst  &= reverse_mask_xor[src_len_modulo]; 
       *dst |= reverse_mask[src_len_modulo]  & *src; 
      } 
     } else { 
      int    bit_diff_ls, 
          bit_diff_rs; 
      int    byte_len; 
      int    src_len_modulo; 
      unsigned char c; 
      /* 
      * Begin: Line things up on destination. 
      */ 
      if (src_offset_modulo > dst_offset_modulo) { 
       bit_diff_ls = src_offset_modulo - dst_offset_modulo; 
       bit_diff_rs = CHAR_BIT - bit_diff_ls; 

       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       c  &= reverse_mask_xor[dst_offset_modulo]; 
      } else { 
       bit_diff_rs = dst_offset_modulo - src_offset_modulo; 
       bit_diff_ls = CHAR_BIT - bit_diff_rs; 

       c = *src >> bit_diff_rs  & 
        reverse_mask_xor[dst_offset_modulo]; 
      } 
      PREPARE_FIRST_COPY(); 
      *dst++ |= c; 

      /* 
      * Middle: copy with only shifting the source. 
      */ 
      byte_len = src_len/CHAR_BIT; 

      while (--byte_len >= 0) { 
       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       *dst++ = c; 
      } 

      /* 
      * End: copy the remaing bits; 
      */ 
      src_len_modulo = src_len % CHAR_BIT; 
      if (src_len_modulo) { 
       c = *src++ << bit_diff_ls; 
       c |= *src >> bit_diff_rs; 
       c  &= reverse_mask[src_len_modulo]; 

       *dst  &= reverse_mask_xor[src_len_modulo]; 
       *dst |= c; 
      } 
     } 
    } 
}