时间戳

首页 > 解决方案 > How to optimize reversing the order of groups of bits

c - How to optimize reversing the order of groups of bits

问题描述

Basically, I have 8 pieces of data, 2 bits each (4 states), being stored in the 16 LSBs of a 32-bit integer. I want to reverse the order of the data pieces to do some pattern matching.

I am given a reference integer and 8 candidates, and I need to match one of the candidates to the reference. However, the matching candidate may be transformed in some predictable way.

If the reference data is in the form [0,1,2,3,4,5,6,7], then the possible matches can be in one of these 8 forms:

[0,1,2,3,4,5,6,7], [0,7,6,5,4,3,2,1]
[6,7,0,1,2,3,4,5], [2,1,0,7,6,5,4,3]
[4,5,6,7,0,1,2,3], [4,3,2,1,0,7,6,5]
[2,3,4,5,6,7,0,1], [6,5,4,3,2,1,0,7]

The pattern is that the data is always in order, but can be reversed and rotated.

I am implementing this in C and MIPS. I have both working, but they seem bulky. My current approach is to mask each piece from the original, shift it to its new position, and OR it with the new variable (initialized to 0).

I did more hard coding in C:

int ref = 4941; // reference value, original order [1,3,0,1,3,0,1,0], (encoded as 0b0001001101001101)
int rev = 0;
rev |= ((ref & 0x0003) << 14) | ((ref & 0x000C) << 10) | ((ref & 0x0030) << 6) | ((ref & 0x00C0) << 2); // move bottom 8 bits to top
rev |= ((ref & 0xC000) >> 14) | ((ref & 0x3000) >> 10) | ((ref & 0x0C00) >> 6) | ((ref & 0x0300) >> 2); // move top 8 bits to bottom
// rev = 29124 reversed order [0,1,0,3,1,0,3,1], (0b0111000111000100)

I implemented a loop in MIPS to try to reduce the static instructions:

        lw      $01, Reference($00) # load reference value
        addi    $04, $00, 4         # initialize $04 as Loop counter
        addi    $05, $00, 14            # initialize $05 to hold shift value
        addi    $06, $00, 3         # initialize $06 to hold mask (one piece of data)

# Reverse the order of data in Reference and store it in $02
Loop:   addi    $04, $04, -1            # decrement Loop counter
        and     $03, $01, $06       # mask out one piece ($03 = Reference & $06) 
        sllv    $03, $03, $05       # shift piece to new position ($03 <<= $05)
        or      $02, $02, $03       # put piece into $02 ($02 |= $03)
        sllv    $06, $06, $05       # shift mask for next piece
        and     $03, $01, $06       # mask out next piece (#03 = Reference & $06)
        srlv    $03, $03, $05       # shift piece to new position ($03 >>= $05)
        or      $02, $02, $03       # put new piece into $02 ($02 |= $03)
        srlv    $06, $06, $05       # shift mask back
        addi    $05, $05, -4            # decrease shift amount by 4
        sll     $06, $06, 2         # shift mask for next loop
        bne     $04, $00, Loop      # keep looping while $04 != 0

Is there a way to implement this that is simpler or at least fewer instructions?

标签： cmips

解决方案

要反转您的位，您可以使用以下代码。

static int rev(int v){
  // swap adjacent pairs of bits
  v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
  // swap nibbles
  v = ((v >> 4) & 0x0f0f) | ((v & 0x0f0f) << 4);
  // swap bytes
  v = ((v >> 8) & 0x00ff) | ((v & 0x00ff) << 8);
  return v;
}

MIPS 实现是 15 条指令。

rev: # value to reverse in $01
     # uses $02 reg
   srli $02, $01, 2
   andi $02, $02, 0x3333
   andi $01, $01, 0x3333
   slli $01, $01, 2
   or   $01, $01, $02
   srli $02, $01, 4
   andi $02, $02, 0x0f0f
   andi $01, $01, 0x0f0f
   slli $01, $01, 4
   or   $01, $01, $02
   srli $02, $01, 8
   andi $02, $02, 0xff
   andi $01, $01, 0xff
   slli $01, $01, 8
   or   $01, $01, $02
   # result in $01

请注意，您可以通过将常量加倍（甚至在 64 位机器上为 4）来同时反转 2x16 位。但我不确定它在你的情况下是否有用。

推荐阅读