我有一个问题要解决,但我不知道如何解决。我想知道如何解决这个问题。我有一个内存地址,在ESI中。内存表示某种简化的ASCII编码,其中5位一个接一个地表示特定字符。存储器以5位(00000b)结束。为了转换为正常的8位ASCII,必须将60H添加到每个5位值。我想将每个5位编码的字符存储为地址EDI下编码的8位ASCII。EDI也必须以0-00000000b结尾。
示例:[ESI]=00011 00010 11010 00000b[EDI]=01100011 01100010 01111010 00000000 b
我将如何从esi中一个接一个地提取每5个比特?
首先,您需要确定5位代码在输入字节流中的排列方式。
我们需要从整个输入数据字节开始:如果我们说[ESI]=00011 00010 11010 00000,我们将跳过解释和解码8位字节的重要第一步
就像endian-ness一样,有两种合理的方法可以做到这一点。其中一个更适合英特尔指令集。
76543210 bit numbering position
+--------+
| | first input data byte
+--------+
..... (A) possible position of 5-bit code within first input byte
..... (B) alternate position of 5-bit code within first input byte
选择(A)表示第一个5位代码位于第一个输入数据字节的最低有效位,而选择(B)表示第一5位代码处于第一个输入的数据字节的最高有效位。
由于intel机器是小端序,从LSB到MSB都是数字位,因此在该处理器上选择(A)更为自然。
选项(A)将按如下方式查看输入字节流:
1 2 3 input byte stream byte number
76543210 76543210 76543210 input byte bit position numbers
hgfedcba ponmlkji xwvutsrq input byte stream, individual bits as letters
22211111 43333322 55554444 5-bit code number for each bit
/ /
/ / | |
/ / | |
/ / | |
edcba jihgf onmlk tsrqp yxwvu 5-bit code output stream
1 2 3 4 5 5-bit code output number
您可以看到5位代码#2的位跨越字节边界,5位代码#4也是如此。
对于选项(B),视图将如下所示:
1 2 3 input byte stream byte number
76543210 76543210 76543210 input byte bit position numbers
abcdefgh ijklmnop qrstuvwx input byte stream, individual bits as letters
11111222 22333334 44445555 5-bit code number for each bit
| | | \
| | | | \ |
| | | | | | |
abcde fghij klmno pqrst uvwxy 5-bit code output stream
1 2 3 4 5 5-bit code output number
这更像是你在文本中显示的内容,所以你真的需要弄清楚该使用哪个选项。具体示例将显示第一个5位代码在第一个数据字节中的位置。
无论哪种方式,一种方法都是输入8位字节并输出5位代码!
处理大小不匹配的方法是使用位队列(可变长度)作为缓冲区,并且只要位队列中的位计数小于5,就有条件地将整个输入字节放入位队列。
(这是一种缓冲方法;缓冲在任何地方都使用,例如当应用程序想要输入或输出字符/字节(想想printf
和文本行),而设备(如文件系统)想要写入块(4096的块)时,为了满足大小不匹配)
因此,bit_queue的大小是4(最大值不足以生成5位代码)+8(一个全新的字节)=队列中最多12位——因此,bit_ queue将适合16位寄存器,此外,我们还需要另一个变量作为bit count(最大值12)。
基本上,我们可以有一个循环,对于每次迭代,总是输出一个5位代码,而有条件地消耗一个8位输入数据字节(例如,在需要时)。这种方法将为队列提供足够的比特,以便在每次迭代中输出5比特代码。
更正式的:
int bit_count = 0;
uint_16 bit_queue = 0;
loop:
if bit_count < 5 then // need to add more bits? so get a byte
temp8 = *sourcePointer++ // fetch byte/8-bits from memory
temp16 = temp8 // zero extend temp8 to 16 bits
// to match the size of bit_queue
bit_queue = merge(bit_queue, temp16)
bit_count += 8 // we just added 8 bits to the bit queue
endif
temp5 = extract5(bit_queue) // take the 5 bits of interest
bit_queue = remove5(bit_queue) // discard 5 bit code from the bit queue
bit_count -= 5 // we just removed 5 bits from bit queue
*destinationPointer++ = temp5 + 0x60
if temp5 != 0 goto loop
我已经在伪代码中编写了merge、extract5和remove5作为函数,但它们是简单的Shift、Or和Mask逻辑操作,需要内联完成(而不是调用函数)。
将它们更抽象地显示为函数的原因是,它们的确切定义取决于(A)与(B)的选择。
对于选择(A),来自每个下一个输入数据字节的新的8位被定位在队列的高(更有效)侧,并且5位代码被从位队列的LSB部分移除,而对于选择(B),相反的是,来自每个上一个输入数据字节的新8位被放置在队列的低/LSB侧,并且五位代码被从位队列的MSB部分移除。
使用选项(A)的示例:
最初,bit_queue为空,bit_count为零。因此,将输入数据字节输入到bit_queue的条件操作简单地将第一个数据字节加载到bit_queue(合并操作与空队列合并,因此将是零位置的退化移位,并且简单地按原样复制值。)
00000000hgfedcba bit_queue loaded with first byte
8 bit_count
函数extract5。5位代码只是0x1f的位队列的掩码,产生
00000000hgfedcba bit_queue loaded with first byte
0000000000011111 mask, 0x1f
----------------- & mask operation
00000000000edcba 5-bit code result
我们可以添加0x60并将其发送到输出数据流。
下一个函数remove5:
bit_queue >>= 5 discard 5 bits by shifting them off the end
00000000hgfedcba bit_queue: before shift
0000000000000hgf bit_queue: after shift
请注意,对于删除,我们还将bit_count递减5,表示bit_queue中只剩下3个比特。
最后merge,它将bit_queue和temp16作为输入(这是在第二次迭代中):
0000000000000hgf bit_queue: remaining bits after shift
00000000ponmlkji temp16: next input data byte, zero extended to 16 bits
我们需要改变温度16;i〃;在temp16中;0";在";h〃;在bit_queue中。移位量就是bit_count:这就是我们需要在bit_queue中保留的比特数,所以通过将temp16移位该量,这将在输入字节的数据之后插入bit_count零。
temp16 <<= bit_count // bit_count is 3
00000000ponmlkji temp16: before shift
00000ponmlkji000 temp16: after shift
最后;或";将移位后的temp16合并到bit_queue:中的操作
0000000000000hgf bit_queue after removing the first 5 bits
00000ponmlkji000 temp16: next input data byte, shifted
----------------- | or operation
00000ponmlkjihgf new bit_queue after merge operation,
holding 3 bits from input data byte 1,
and 8 bits from input data byte 2
请注意,bit_count现在变为3+8=11。
这个位队列现在可以提供另一个5位代码,依此类推
这种方法的一个优点是,它不需要处理器的未对齐加载能力,因此适用于MIPS和x86。它还只加载每个输入数据字节一次。
作为一种完全替代的方法,我们可以从其索引/位置号及其占用的两个相邻字节中提取任何给定的5位值。这样,我们只需提取每个5位的值。
提取5位值首先通过计算5位值的第一位的位位置偏移来完成,该偏移可用于计算(最多)保持5位字段的两个字节的字节偏移,以及提取该字段的偏移量
比特位置偏移是通过将5比特索引乘以5来计算的(或者如果在线性循环中进行,则每次迭代都将5加到比特位置计数器)。字节偏移量是通过将该比特位置偏移量除以8来计算的(整数除法楼层,这里除以8是3的简单右移)。最后,再加上输入数组的基,我们得到了包含该5位索引处的5位值的第一位的字节地址。由于5比特字段在第一个字节中至少有一个比特,因此它要么完全包含在第一个比特中,要么是第一个字节和下一个连续字节的组合,因此我们可以在该地址加载16比特值,并使整个5比特字段可用。
5位字段的扫描结果如下:
bit_offset = 0
loop:
byte_offset = bit_offset >> 3
address = sourcePointer + byte_offset // regular/unscaled addition
temp16 = *address // this is a 16-bit load ***
temp16 = temp16 >> bit_offset
temp8 = temp16 & 0x1f
*destinationPointer++ = temp8 + 0x60
bit_offset += 5
if temp8 != 0 goto loop
***
这种方法在5位索引处加载两个字节,无论是否需要,同时将下一次迭代的字节位置最多增加1个字节。它多次重新加载输入流的每个字节。它将潜在感兴趣的两个字节加载到16位数据中,然后移位以提取感兴趣的5位字段。它依赖于未对齐的访问,尽管它可以通过相当简单的两字节加载和重新组装序列轻松地适用于不支持未对齐访问的硬件。