On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
> Ivan Godard wrote:
> > On 1/12/2022 2:46 PM, MitchAlsup wrote:
> >> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
> >>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
> >>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
> >>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
> >>>>>
> >>>>>> So, what does (13 << -7) mean ?
> >>>>> From the replies, I see that this is a completely different
> >>>>> can of worms. I would tend to favor the VAX interpretation,
> >>>>> but it's unclear to me that it would be worth the extra
> >>>>> run-time overhead that it might imply.
> >>>> <
> >>>> The VAX interpretation does not allow for shifts to be used as
> >>>> bit-manipulation instructions (extract signed and unsigned).
> >> <
> >>> That turns into a rotate and a shft right. But isn't that what a
> >>> hardware EXTR is going to do anyway?
> >> <
> >> Technically an extract is:
> >> <
> >> r = ((c << (containerWidth - fieldWidth - offset)) >>
> >> (containerWidth-fieldWidth));
> >> <
> >> However, what we do in HW is:
> >> <
> >> m = tableM[fieldWidth]; // mask m:: often done
> >> with table
> >> s = ~0u << (fieldWidth+offset); // sign extension bits ::
> >> often done with table
> >> t = (c >> offset) & m | ( signed || (c & ( 1 <<
> >> (fieldWidth+offset)) ? s : 0);
> >> <
> >> as this uses 1 shifter and either tables or greater-than decoders.
> >> <
> >> But the part I was hinting at is that we have a large container for
> >> this shift
> >> count and we need only a few bits on one end. So, in My 66000, the
> >> upper ½
> >> of the container is allowed to contain a value 0..64 (where both 0 and 64
> >> mean 64-bit field width).
> >> <
> >> Done this way, shifts are degenerate subsets of EXT.
> >> <
> >> If you use the sign bit<63> to control shift direction, you probably
> >> should not
> >> be using bits<37:32> as the field width because pasting the fieldWidth
> >> into
> >> such a container is simply harder.
> >> <
> >> I learned the hard way about placing both containers too close together
> >> in the Mc 88100.
> >
> > Hmm. So the container is a field descriptor. But it's not actually a
> > bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
> > IIRC. Gives you some encoding entropy, but not actually any new
> > semantic, and you have to build the descriptor, which you avoid when
> > offset and width are separate arguments.
> >
> > Where ISAs really fall down is parsing a bit stream: grab a dynamic
> > number of bits off the front of a bit stream, advancing the stream; word
> > boundaries are not significant. The problem is that HW provides word
> > streams (loop/load) and mapping that to a bit stream is nasty. The logic
> > is the same as mapping a line stream into a (VL) instruction stream in
> > the decoder's instruction buffer, but how to represent that in an ISA?
> We did use to have something like that back in the PDP days with the
> variable-sized load byte opcode that would automatically step forward to
> the next work if needed.
>
> Today we would need a separate hw mechanism for that bitstream buffer,
> and probably a filling mechanism which either would need to be
> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
> would load the next (8/16/32 bits into the target register at offs bit
> offset, updating the OFFS reg and SRC pointer, but only if there was
> room, otherwise it is a NOP. The main problem is the need to update all
> three register operands. :-(
>
> Having it would however make it far easier to handle arbitrary bit
> streams, avoiding the current need for branchy code.
<
What is wrong with having a container 2× as large as the largest bit-field
then use a shift-double to position the bits at an appropriate
place for extraction and then decoding/encoding.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

On 1/13/2022 7:54 AM, MitchAlsup wrote:
> On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
>> Ivan Godard wrote:
>>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
>>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
>>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
>>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
>>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
>>>>>>>
>>>>>>>> So, what does (13 << -7) mean ?
>>>>>>> From the replies, I see that this is a completely different
>>>>>>> can of worms. I would tend to favor the VAX interpretation,
>>>>>>> but it's unclear to me that it would be worth the extra
>>>>>>> run-time overhead that it might imply.
>>>>>> <
>>>>>> The VAX interpretation does not allow for shifts to be used as
>>>>>> bit-manipulation instructions (extract signed and unsigned).
>>>> <
>>>>> That turns into a rotate and a shft right. But isn't that what a
>>>>> hardware EXTR is going to do anyway?
>>>> <
>>>> Technically an extract is:
>>>> <
>>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
>>>> (containerWidth-fieldWidth));
>>>> <
>>>> However, what we do in HW is:
>>>> <
>>>> m = tableM[fieldWidth]; // mask m:: often done
>>>> with table
>>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
>>>> often done with table
>>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
>>>> (fieldWidth+offset)) ? s : 0);
>>>> <
>>>> as this uses 1 shifter and either tables or greater-than decoders.
>>>> <
>>>> But the part I was hinting at is that we have a large container for
>>>> this shift
>>>> count and we need only a few bits on one end. So, in My 66000, the
>>>> upper ½
>>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
>>>> mean 64-bit field width).
>>>> <
>>>> Done this way, shifts are degenerate subsets of EXT.
>>>> <
>>>> If you use the sign bit<63> to control shift direction, you probably
>>>> should not
>>>> be using bits<37:32> as the field width because pasting the fieldWidth
>>>> into
>>>> such a container is simply harder.
>>>> <
>>>> I learned the hard way about placing both containers too close together
>>>> in the Mc 88100.
>>>
>>> Hmm. So the container is a field descriptor. But it's not actually a
>>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
>>> IIRC. Gives you some encoding entropy, but not actually any new
>>> semantic, and you have to build the descriptor, which you avoid when
>>> offset and width are separate arguments.
>>>
>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>> number of bits off the front of a bit stream, advancing the stream; word
>>> boundaries are not significant. The problem is that HW provides word
>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>> is the same as mapping a line stream into a (VL) instruction stream in
>>> the decoder's instruction buffer, but how to represent that in an ISA?
>> We did use to have something like that back in the PDP days with the
>> variable-sized load byte opcode that would automatically step forward to
>> the next work if needed.
>>
>> Today we would need a separate hw mechanism for that bitstream buffer,
>> and probably a filling mechanism which either would need to be
>> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
>> would load the next (8/16/32 bits into the target register at offs bit
>> offset, updating the OFFS reg and SRC pointer, but only if there was
>> room, otherwise it is a NOP. The main problem is the need to update all
>> three register operands. :-(
>>
>> Having it would however make it far easier to handle arbitrary bit
>> streams, avoiding the current need for branchy code.
> <
> What is wrong with having a container 2× as large as the largest bit-field
> then use a shift-double to position the bits at an appropriate
> place for extraction and then decoding/encoding.

What's wrong is the need to conditionally refill and then merge the
loaded value into the shift pair. The condition is totally
unpredictable, so you get a miss every <word size>/<average request
size> cycles. We have predicated loads and isomorphic shifts, but have
only enough slots to do a reasonable job on a Gold.

Try it on my66: input is an array of request bit-sizes, an input array
of bits, an output array of words, and a count. Unpack the consecutive
bit-size fields from the bits into the words.

Have fun.

On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> On 1/13/2022 7:54 AM, MitchAlsup wrote:
> > On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
> >> Ivan Godard wrote:
> >>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
> >>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
> >>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
> >>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
> >>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
> >>>>>>>
> >>>>>>>> So, what does (13 << -7) mean ?
> >>>>>>> From the replies, I see that this is a completely different
> >>>>>>> can of worms. I would tend to favor the VAX interpretation,
> >>>>>>> but it's unclear to me that it would be worth the extra
> >>>>>>> run-time overhead that it might imply.
> >>>>>> <
> >>>>>> The VAX interpretation does not allow for shifts to be used as
> >>>>>> bit-manipulation instructions (extract signed and unsigned).
> >>>> <
> >>>>> That turns into a rotate and a shft right. But isn't that what a
> >>>>> hardware EXTR is going to do anyway?
> >>>> <
> >>>> Technically an extract is:
> >>>> <
> >>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
> >>>> (containerWidth-fieldWidth));
> >>>> <
> >>>> However, what we do in HW is:
> >>>> <
> >>>> m = tableM[fieldWidth]; // mask m:: often done
> >>>> with table
> >>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
> >>>> often done with table
> >>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
> >>>> (fieldWidth+offset)) ? s : 0);
> >>>> <
> >>>> as this uses 1 shifter and either tables or greater-than decoders.
> >>>> <
> >>>> But the part I was hinting at is that we have a large container for
> >>>> this shift
> >>>> count and we need only a few bits on one end. So, in My 66000, the
> >>>> upper ½
> >>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
> >>>> mean 64-bit field width).
> >>>> <
> >>>> Done this way, shifts are degenerate subsets of EXT.
> >>>> <
> >>>> If you use the sign bit<63> to control shift direction, you probably
> >>>> should not
> >>>> be using bits<37:32> as the field width because pasting the fieldWidth
> >>>> into
> >>>> such a container is simply harder.
> >>>> <
> >>>> I learned the hard way about placing both containers too close together
> >>>> in the Mc 88100.
> >>>
> >>> Hmm. So the container is a field descriptor. But it's not actually a
> >>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
> >>> IIRC. Gives you some encoding entropy, but not actually any new
> >>> semantic, and you have to build the descriptor, which you avoid when
> >>> offset and width are separate arguments.
> >>>
> >>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
> >>> number of bits off the front of a bit stream, advancing the stream; word
> >>> boundaries are not significant. The problem is that HW provides word
> >>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
> >>> is the same as mapping a line stream into a (VL) instruction stream in
> >>> the decoder's instruction buffer, but how to represent that in an ISA?
> >> We did use to have something like that back in the PDP days with the
> >> variable-sized load byte opcode that would automatically step forward to
> >> the next work if needed.
> >>
> >> Today we would need a separate hw mechanism for that bitstream buffer,
> >> and probably a filling mechanism which either would need to be
> >> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
> >> would load the next (8/16/32 bits into the target register at offs bit
> >> offset, updating the OFFS reg and SRC pointer, but only if there was
> >> room, otherwise it is a NOP. The main problem is the need to update all
> >> three register operands. :-(
> >>
> >> Having it would however make it far easier to handle arbitrary bit
> >> streams, avoiding the current need for branchy code.
> > <
> > What is wrong with having a container 2× as large as the largest bit-field
> > then use a shift-double to position the bits at an appropriate
> > place for extraction and then decoding/encoding.
> What's wrong is the need to conditionally refill and then merge the
> loaded value into the shift pair. The condition is totally
> unpredictable, so you get a miss every <word size>/<average request
> size> cycles. We have predicated loads and isomorphic shifts, but have
> only enough slots to do a reasonable job on a Gold.
>
> Try it on my66: input is an array of request bit-sizes, an input array
> of bits, an output array of words, and a count. Unpack the consecutive
> bit-size fields from the bits into the words.
>
> Have fun.
<
I came up with this in 5 minutes::
This assumes the input bit-length selector is an vector of characters and that the
chars contain values from {1..64}
<
void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
{ uint64_t len,
bit=0,
word=0,
extract,
container1 = packed[0],
container2 = packed[1];

for( unsigned int i = 0; i < count; i++ )
{
len = size[i];
bit += len;
extract = ( len << 32 ) | ( bit & 0x3F );
if( word != bit >> 6 )
{
container1 = container2;
container2 = packed[++word];
}
unpacked[i] = {container2, container1} >> extract;
}
} <
This translates into pretty nice My 66000 ISA:
<
ENTRY unpack
unpack:
MOV R5,#0
MOV R6,#0
LDD R7,[R2]
LDD R8,[R2+8]
MOV R9,#0
loop:
LDUB R10,[R1+R9]
ADD R5,R5,R10
AND R11,R5,#63
SL R12,R10,#32
OR R11,R11,R12
SR R12,R6,#6
CMP R11,R6,R12
PEQ R11,{111}
ADD R6,R6,#1
MOV R7,R8
LDD R8,[R2+R6<<3]
CARRY R8,{{I}}
SL R12,R7,R11
STD R12,[R3+R9<<3]
ADD R9,R9,#1
CMP R11,R9,R4
BLT R11,loop
RET
<
Well at least straightforwardly.

MitchAlsup wrote:
> On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
>> Ivan Godard wrote:
>>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
>>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
>>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
>>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
>>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
>>>>>>>
>>>>>>>> So, what does (13 << -7) mean ?
>>>>>>> From the replies, I see that this is a completely different
>>>>>>> can of worms. I would tend to favor the VAX interpretation,
>>>>>>> but it's unclear to me that it would be worth the extra
>>>>>>> run-time overhead that it might imply.
>>>>>> <
>>>>>> The VAX interpretation does not allow for shifts to be used as
>>>>>> bit-manipulation instructions (extract signed and unsigned).
>>>> <
>>>>> That turns into a rotate and a shft right. But isn't that what a
>>>>> hardware EXTR is going to do anyway?
>>>> <
>>>> Technically an extract is:
>>>> <
>>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
>>>> (containerWidth-fieldWidth));
>>>> <
>>>> However, what we do in HW is:
>>>> <
>>>> m = tableM[fieldWidth]; // mask m:: often done
>>>> with table
>>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
>>>> often done with table
>>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
>>>> (fieldWidth+offset)) ? s : 0);
>>>> <
>>>> as this uses 1 shifter and either tables or greater-than decoders.
>>>> <
>>>> But the part I was hinting at is that we have a large container for
>>>> this shift
>>>> count and we need only a few bits on one end. So, in My 66000, the
>>>> upper ½
>>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
>>>> mean 64-bit field width).
>>>> <
>>>> Done this way, shifts are degenerate subsets of EXT.
>>>> <
>>>> If you use the sign bit<63> to control shift direction, you probably
>>>> should not
>>>> be using bits<37:32> as the field width because pasting the fieldWidth
>>>> into
>>>> such a container is simply harder.
>>>> <
>>>> I learned the hard way about placing both containers too close together
>>>> in the Mc 88100.
>>>
>>> Hmm. So the container is a field descriptor. But it's not actually a
>>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
>>> IIRC. Gives you some encoding entropy, but not actually any new
>>> semantic, and you have to build the descriptor, which you avoid when
>>> offset and width are separate arguments.
>>>
>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>> number of bits off the front of a bit stream, advancing the stream; word
>>> boundaries are not significant. The problem is that HW provides word
>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>> is the same as mapping a line stream into a (VL) instruction stream in
>>> the decoder's instruction buffer, but how to represent that in an ISA?
>> We did use to have something like that back in the PDP days with the
>> variable-sized load byte opcode that would automatically step forward to
>> the next work if needed.
>>
>> Today we would need a separate hw mechanism for that bitstream buffer,
>> and probably a filling mechanism which either would need to be
>> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
>> would load the next (8/16/32 bits into the target register at offs bit
>> offset, updating the OFFS reg and SRC pointer, but only if there was
>> room, otherwise it is a NOP. The main problem is the need to update all
>> three register operands. :-(
>>
>> Having it would however make it far easier to handle arbitrary bit
>> streams, avoiding the current need for branchy code.
> <
> What is wrong with having a container 2× as large as the largest bit-field
> then use a shift-double to position the bits at an appropriate
> place for extraction and then decoding/encoding.

This is indeed the most obvious solution, the only reason I haven't used
it generally is because on some x86 cores, SHRD/SHLD (plus SHR/SHL of
the top half) have been 4x slower than just SHR/SHL, and that made it
faster to use a single reg and a branchful (or even branchless) update.

Make the shifter double-wide by default (as you already need for FMAC),
and that problem goes away.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
>> On 1/13/2022 7:54 AM, MitchAlsup wrote:
>>> On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
>>>> Ivan Godard wrote:
>>>>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
>>>>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
>>>>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
>>>>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
>>>>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
>>>>>>>>>
>>>>>>>>>> So, what does (13 << -7) mean ?
>>>>>>>>> From the replies, I see that this is a completely different
>>>>>>>>> can of worms. I would tend to favor the VAX interpretation,
>>>>>>>>> but it's unclear to me that it would be worth the extra
>>>>>>>>> run-time overhead that it might imply.
>>>>>>>> <
>>>>>>>> The VAX interpretation does not allow for shifts to be used as
>>>>>>>> bit-manipulation instructions (extract signed and unsigned).
>>>>>> <
>>>>>>> That turns into a rotate and a shft right. But isn't that what a
>>>>>>> hardware EXTR is going to do anyway?
>>>>>> <
>>>>>> Technically an extract is:
>>>>>> <
>>>>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
>>>>>> (containerWidth-fieldWidth));
>>>>>> <
>>>>>> However, what we do in HW is:
>>>>>> <
>>>>>> m = tableM[fieldWidth]; // mask m:: often done
>>>>>> with table
>>>>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
>>>>>> often done with table
>>>>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
>>>>>> (fieldWidth+offset)) ? s : 0);
>>>>>> <
>>>>>> as this uses 1 shifter and either tables or greater-than decoders.
>>>>>> <
>>>>>> But the part I was hinting at is that we have a large container for
>>>>>> this shift
>>>>>> count and we need only a few bits on one end. So, in My 66000, the
>>>>>> upper ½
>>>>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
>>>>>> mean 64-bit field width).
>>>>>> <
>>>>>> Done this way, shifts are degenerate subsets of EXT.
>>>>>> <
>>>>>> If you use the sign bit<63> to control shift direction, you probably
>>>>>> should not
>>>>>> be using bits<37:32> as the field width because pasting the fieldWidth
>>>>>> into
>>>>>> such a container is simply harder.
>>>>>> <
>>>>>> I learned the hard way about placing both containers too close together
>>>>>> in the Mc 88100.
>>>>>
>>>>> Hmm. So the container is a field descriptor. But it's not actually a
>>>>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
>>>>> IIRC. Gives you some encoding entropy, but not actually any new
>>>>> semantic, and you have to build the descriptor, which you avoid when
>>>>> offset and width are separate arguments.
>>>>>
>>>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>>>> number of bits off the front of a bit stream, advancing the stream; word
>>>>> boundaries are not significant. The problem is that HW provides word
>>>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>>>> is the same as mapping a line stream into a (VL) instruction stream in
>>>>> the decoder's instruction buffer, but how to represent that in an ISA?
>>>> We did use to have something like that back in the PDP days with the
>>>> variable-sized load byte opcode that would automatically step forward to
>>>> the next work if needed.
>>>>
>>>> Today we would need a separate hw mechanism for that bitstream buffer,
>>>> and probably a filling mechanism which either would need to be
>>>> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
>>>> would load the next (8/16/32 bits into the target register at offs bit
>>>> offset, updating the OFFS reg and SRC pointer, but only if there was
>>>> room, otherwise it is a NOP. The main problem is the need to update all
>>>> three register operands. :-(
>>>>
>>>> Having it would however make it far easier to handle arbitrary bit
>>>> streams, avoiding the current need for branchy code.
>>> <
>>> What is wrong with having a container 2× as large as the largest bit-field
>>> then use a shift-double to position the bits at an appropriate
>>> place for extraction and then decoding/encoding.
>> What's wrong is the need to conditionally refill and then merge the
>> loaded value into the shift pair. The condition is totally
>> unpredictable, so you get a miss every <word size>/<average request
>> size> cycles. We have predicated loads and isomorphic shifts, but have
>> only enough slots to do a reasonable job on a Gold.
>>
>> Try it on my66: input is an array of request bit-sizes, an input array
>> of bits, an output array of words, and a count. Unpack the consecutive
>> bit-size fields from the bits into the words.
>>
>> Have fun.
> <
> I came up with this in 5 minutes::
> This assumes the input bit-length selector is an vector of characters and that the
> chars contain values from {1..64}
> <
> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> {
> uint64_t len,
> bit=0,
> word=0,
> extract,
> container1 = packed[0],
> container2 = packed[1];
>
> for( unsigned int i = 0; i < count; i++ )
> {
> len = size[i];
> bit += len;
> extract = ( len << 32 ) | ( bit & 0x3F );
> if( word != bit >> 6 )
> {
> container1 = container2;
> container2 = packed[++word];
> }
> unpacked[i] = {container2, container1} >> extract;
> }
> }
> <
> This translates into pretty nice My 66000 ISA:
> <
> ENTRY unpack
> unpack:
> MOV R5,#0
> MOV R6,#0
> LDD R7,[R2]
> LDD R8,[R2+8]
> MOV R9,#0
> loop:
> LDUB R10,[R1+R9]
> ADD R5,R5,R10
> AND R11,R5,#63
> SL R12,R10,#32
> OR R11,R11,R12
> SR R12,R6,#6
> CMP R11,R6,R12
> PEQ R11,{111}
> ADD R6,R6,#1
> MOV R7,R8
> LDD R8,[R2+R6<<3]
> CARRY R8,{{I}}
> SL R12,R7,R11
> STD R12,[R3+R9<<3]
> ADD R9,R9,#1
> CMP R11,R9,R4
> BLT R11,loop
> RET
> <
> Well at least straightforwardly.
>

Here you are taking full advantage of both predicate shadows to do the
branchless buffer update and your CARRY-enabled double-wide combined
shift/extract operation. The latter is somewhat broken here since you
would need a compiler intrinsic instead of directly passing the length
field in the top 32 bits of the shift count. I.e. this is NOT valid C afaik?

OTOH, it does show nicely how those two features allow very efficient
implementation of a very common but currenlty quite expensive building
block.

One small wrinkle: You very often want to have that bit picker inlined
in a lot of different locations, instead of it being a sentral function
you call, this is similar to typical C stdio libraries where the
single-byte io functions are macros which conditionally call filler
functions only when needed.

For a Huffman style decompressor you don't know how many bits you need
until after you've read them, so there you have to extract enough bits
for a subsequent table lookup which either tells you how many to keep,
along with the value of the lookup, or a flag which indicates more bits
are needed:

On Thursday, January 13, 2022 at 1:26:00 PM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> >> On 1/13/2022 7:54 AM, MitchAlsup wrote:
> >>> On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
> >>>> Ivan Godard wrote:
> >>>>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
> >>>>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
> >>>>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
> >>>>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
> >>>>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
> >>>>>>>>>
> >>>>>>>>>> So, what does (13 << -7) mean ?
> >>>>>>>>> From the replies, I see that this is a completely different
> >>>>>>>>> can of worms. I would tend to favor the VAX interpretation,
> >>>>>>>>> but it's unclear to me that it would be worth the extra
> >>>>>>>>> run-time overhead that it might imply.
> >>>>>>>> <
> >>>>>>>> The VAX interpretation does not allow for shifts to be used as
> >>>>>>>> bit-manipulation instructions (extract signed and unsigned).
> >>>>>> <
> >>>>>>> That turns into a rotate and a shft right. But isn't that what a
> >>>>>>> hardware EXTR is going to do anyway?
> >>>>>> <
> >>>>>> Technically an extract is:
> >>>>>> <
> >>>>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
> >>>>>> (containerWidth-fieldWidth));
> >>>>>> <
> >>>>>> However, what we do in HW is:
> >>>>>> <
> >>>>>> m = tableM[fieldWidth]; // mask m:: often done
> >>>>>> with table
> >>>>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
> >>>>>> often done with table
> >>>>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
> >>>>>> (fieldWidth+offset)) ? s : 0);
> >>>>>> <
> >>>>>> as this uses 1 shifter and either tables or greater-than decoders.
> >>>>>> <
> >>>>>> But the part I was hinting at is that we have a large container for
> >>>>>> this shift
> >>>>>> count and we need only a few bits on one end. So, in My 66000, the
> >>>>>> upper ½
> >>>>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
> >>>>>> mean 64-bit field width).
> >>>>>> <
> >>>>>> Done this way, shifts are degenerate subsets of EXT.
> >>>>>> <
> >>>>>> If you use the sign bit<63> to control shift direction, you probably
> >>>>>> should not
> >>>>>> be using bits<37:32> as the field width because pasting the fieldWidth
> >>>>>> into
> >>>>>> such a container is simply harder.
> >>>>>> <
> >>>>>> I learned the hard way about placing both containers too close together
> >>>>>> in the Mc 88100.
> >>>>>
> >>>>> Hmm. So the container is a field descriptor. But it's not actually a
> >>>>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
> >>>>> IIRC. Gives you some encoding entropy, but not actually any new
> >>>>> semantic, and you have to build the descriptor, which you avoid when
> >>>>> offset and width are separate arguments.
> >>>>>
> >>>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
> >>>>> number of bits off the front of a bit stream, advancing the stream; word
> >>>>> boundaries are not significant. The problem is that HW provides word
> >>>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
> >>>>> is the same as mapping a line stream into a (VL) instruction stream in
> >>>>> the decoder's instruction buffer, but how to represent that in an ISA?
> >>>> We did use to have something like that back in the PDP days with the
> >>>> variable-sized load byte opcode that would automatically step forward to
> >>>> the next work if needed.
> >>>>
> >>>> Today we would need a separate hw mechanism for that bitstream buffer,
> >>>> and probably a filling mechanism which either would need to be
> >>>> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
> >>>> would load the next (8/16/32 bits into the target register at offs bit
> >>>> offset, updating the OFFS reg and SRC pointer, but only if there was
> >>>> room, otherwise it is a NOP. The main problem is the need to update all
> >>>> three register operands. :-(
> >>>>
> >>>> Having it would however make it far easier to handle arbitrary bit
> >>>> streams, avoiding the current need for branchy code.
> >>> <
> >>> What is wrong with having a container 2× as large as the largest bit-field
> >>> then use a shift-double to position the bits at an appropriate
> >>> place for extraction and then decoding/encoding.
> >> What's wrong is the need to conditionally refill and then merge the
> >> loaded value into the shift pair. The condition is totally
> >> unpredictable, so you get a miss every <word size>/<average request
> >> size> cycles. We have predicated loads and isomorphic shifts, but have
> >> only enough slots to do a reasonable job on a Gold.
> >>
> >> Try it on my66: input is an array of request bit-sizes, an input array
> >> of bits, an output array of words, and a count. Unpack the consecutive
> >> bit-size fields from the bits into the words.
> >>
> >> Have fun.
> > <
> > I came up with this in 5 minutes::
> > This assumes the input bit-length selector is an vector of characters and that the
> > chars contain values from {1..64}
> > <
> > void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> > {
> > uint64_t len,
> > bit=0,
> > word=0,
> > extract,
> > container1 = packed[0],
> > container2 = packed[1];
> >
> > for( unsigned int i = 0; i < count; i++ )
> > {
> > len = size[i];
> > bit += len;
> > extract = ( len << 32 ) | ( bit & 0x3F );
> > if( word != bit >> 6 )
> > {
> > container1 = container2;
> > container2 = packed[++word];
> > }
> > unpacked[i] = {container2, container1} >> extract;
> > }
> > }
> > <
> > This translates into pretty nice My 66000 ISA:
> > <
> > ENTRY unpack
> > unpack:
> > MOV R5,#0
> > MOV R6,#0
> > LDD R7,[R2]
> > LDD R8,[R2+8]
> > MOV R9,#0
> > loop:
> > LDUB R10,[R1+R9]
> > ADD R5,R5,R10
> > AND R11,R5,#63
> > SL R12,R10,#32
> > OR R11,R11,R12
> > SR R12,R6,#6
> > CMP R11,R6,R12
> > PEQ R11,{111}
> > ADD R6,R6,#1
> > MOV R7,R8
> > LDD R8,[R2+R6<<3]
> > CARRY R8,{{I}}
> > SL R12,R7,R11
> > STD R12,[R3+R9<<3]
> > ADD R9,R9,#1
> > CMP R11,R9,R4
> > BLT R11,loop
> > RET
> > <
> > Well at least straightforwardly.
> >
> Here you are taking full advantage of both predicate shadows to do the
> branchless buffer update and your CARRY-enabled double-wide combined
> shift/extract operation. The latter is somewhat broken here since you
> would need a compiler intrinsic instead of directly passing the length
> field in the top 32 bits of the shift count. I.e. this is NOT valid C afaik?
<
It is non-portable C that happens to do the right stuff in My 66000 architectures.
>
> OTOH, it does show nicely how those two features allow very efficient
> implementation of a very common but currenlty quite expensive building
> block.
<
Thanks.
>
> One small wrinkle: You very often want to have that bit picker inlined
> in a lot of different locations, instead of it being a sentral function
> you call, this is similar to typical C stdio libraries where the
> single-byte io functions are macros which conditionally call filler
> functions only when needed.
>
> For a Huffman style decompressor you don't know how many bits you need
> until after you've read them,
<
I was just following Ivan's instructions and inserted the requirement that
the length of the maximum field is 64-bits.
<
> so there you have to extract enough bits
> for a subsequent table lookup which either tells you how many to keep,
> along with the value of the lookup, or a flag which indicates more bits
> are needed:
>
> bits9 = get9bits(); // (buffer >> bitsused) & 511;
> vb = bits9table[bits9];
> if (vb.bits > 16) { // More bits needed, use the token field as a
> // secondary table index. Max token len = 16
> bitsused += 9;
> tab = sec_table[vb.token];
> bits7 = get7bits(); // (buffer >> bitsused) & 127;
> vb = tab[bits7];
> }
> token = vb.token;
> bitsused += vb.bits;
> refill(); // buffer |= *word << 32;
> // word += bitsused>>5; bitsused &= 31;
>
> Here the get9bits() and get7bits() calls are macros that blindly pick
> off the next 9/7 bits, starting at bitsused offset into the buffer
> register, but then we would need regular calls to that refill macro
> which makes sure we always have enough bits available to get the next token.
>
> By doing the refills only in one (or a few) central location(s), it
> becomes feasible to have larger/more complicated code to implement it,
> but on x86 I have never been able to gain any time by using branchless
> code (like the example above) to do it.
>
> In theory reloading the same 32-bit value and stuffing it into the high
> half of the 64-bit buffer would only take 5-6 instructions and a couple
> of cycles, but branching around still tends to win, but I haven't tried
> this on a 64-bit platform, i.e. I tended to either reload 16-bit top
> halfs of a 32-bit buffer, or use SHRD on a pair of buffer regs, but in
> the latter case register pressure could get really bad with
> SI/DX:BX/CL/DI all permanently allocated.
<
Had I reversed the field positions in My 66000 ISA encoding, I could
take 3 instructions out of the loop (but this would have made the
more typical shifting operations harder.)
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

Ivan Godard <ivan@millcomputing.com> schrieb:

> Where ISAs really fall down is parsing a bit stream: grab a dynamic
> number of bits off the front of a bit stream, advancing the stream; word
> boundaries are not significant. The problem is that HW provides word
> streams (loop/load) and mapping that to a bit stream is nasty. The logic
> is the same as mapping a line stream into a (VL) instruction stream in
> the decoder's instruction buffer, but how to represent that in an ISA?

The same way that a vector instruction would be represented?

Vectors could be made to operate on sub-word quantities such as bytes,
with microarchitectural SIMD underneath.

I have to confess I do not know much of how compression and
decompression algorithms work. What are the operations that need
to be done with the chunk of bits that is grabbed?

On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> On 1/13/2022 7:54 AM, MitchAlsup wrote:

> What's wrong is the need to conditionally refill and then merge the
> loaded value into the shift pair. The condition is totally
> unpredictable, so you get a miss every <word size>/<average request
> size> cycles. We have predicated loads and isomorphic shifts, but have
> only enough slots to do a reasonable job on a Gold.
>
> Try it on my66: input is an array of request bit-sizes, an input array
> of bits, an output array of words, and a count. Unpack the consecutive
> bit-size fields from the bits into the words.
>
> Have fun.
<
Minor update: had to move a unit of arithmetic so the first field is performed properly.
<
void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
{ uint64_t len,
bit=0,
word=0,
extract,
container1 = packed[0],
container2 = packed[1];

for( unsigned int i = 0; i < count; i++ )
{
len = size[i];
extract = ( len << 32 ) | ( bit & 0x3F );
bit += len;
if( word != bit >> 6 )
{
container1 = container2;
container2 = packed[++word];
}
unpacked[i] = {container2, container1} >> extract;
}
}

On 1/13/2022 12:23 PM, MitchAlsup wrote:
> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
>> On 1/13/2022 7:54 AM, MitchAlsup wrote:
>
>> What's wrong is the need to conditionally refill and then merge the
>> loaded value into the shift pair. The condition is totally
>> unpredictable, so you get a miss every <word size>/<average request
>> size> cycles. We have predicated loads and isomorphic shifts, but have
>> only enough slots to do a reasonable job on a Gold.
>>
>> Try it on my66: input is an array of request bit-sizes, an input array
>> of bits, an output array of words, and a count. Unpack the consecutive
>> bit-size fields from the bits into the words.
>>
>> Have fun.
> <
> Minor update: had to move a unit of arithmetic so the first field is performed properly.
> <
> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> {
> uint64_t len,
> bit=0,
> word=0,
> extract,
> container1 = packed[0],
> container2 = packed[1];
>
> for( unsigned int i = 0; i < count; i++ )
> {
> len = size[i];
> extract = ( len << 32 ) | ( bit & 0x3F );
> bit += len;
> if( word != bit >> 6 )
> {
> container1 = container2;
> container2 = packed[++word];
> }
> unpacked[i] = {container2, container1} >> extract;
> }
> }

Perhaps I'm misreading your double right shift, but doesn't the second
no-reload extraction contain bits from the first? You aren't updating
the containers with a mask.

On Thursday, January 13, 2022 at 4:18:43 PM UTC-6, Ivan Godard wrote:
> On 1/13/2022 12:23 PM, MitchAlsup wrote:
> > On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> >> On 1/13/2022 7:54 AM, MitchAlsup wrote:
> >
> >> What's wrong is the need to conditionally refill and then merge the
> >> loaded value into the shift pair. The condition is totally
> >> unpredictable, so you get a miss every <word size>/<average request
> >> size> cycles. We have predicated loads and isomorphic shifts, but have
> >> only enough slots to do a reasonable job on a Gold.
> >>
> >> Try it on my66: input is an array of request bit-sizes, an input array
> >> of bits, an output array of words, and a count. Unpack the consecutive
> >> bit-size fields from the bits into the words.
> >>
> >> Have fun.
> > <
> > Minor update: had to move a unit of arithmetic so the first field is performed properly.
> > <
> > void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> > {
> > uint64_t len,
> > bit=0,
> > word=0,
> > extract,
> > container1 = packed[0],
> > container2 = packed[1];
> >
> > for( unsigned int i = 0; i < count; i++ )
> > {
> > len = size[i];
> > extract = ( len << 32 ) | ( bit & 0x3F );
> > bit += len;
> > if( word != bit >> 6 )
> > {
> > container1 = container2;
> > container2 = packed[++word];
> > }
> > unpacked[i] = {container2, container1} >> extract;
> > }
> > }
> Perhaps I'm misreading your double right shift, but doesn't the second
> no-reload extraction contain bits from the first? You aren't updating
> the containers with a mask.
<
That is correct. I am leaving the containers in memory format, and extracting
bit-fields from the pair of containers. When it is time to advance the pair of
containers, I copy the second to the first and load a new second (Little Endian
Order).
<
Note that while I use a shift operator (>>); I am performing a bit field extract
because bits<37:32> of the shift count operand contain the size of the field
to be extracted. This is non-portable--but how My 66000 works and how the
industrious programmer can access extract without leaving C. AND you ask
how this could be programmed in my66K (wrong spelling BTW).
<
Essentially, I keep track of the lower bit position of the extracted fields in
two (2) counters {word and bit} and paste in the length of each field on a
per loop basis.

On 1/13/2022 2:37 PM, MitchAlsup wrote:
> On Thursday, January 13, 2022 at 4:18:43 PM UTC-6, Ivan Godard wrote:
>> On 1/13/2022 12:23 PM, MitchAlsup wrote:
>>> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
>>>> On 1/13/2022 7:54 AM, MitchAlsup wrote:
>>>
>>>> What's wrong is the need to conditionally refill and then merge the
>>>> loaded value into the shift pair. The condition is totally
>>>> unpredictable, so you get a miss every <word size>/<average request
>>>> size> cycles. We have predicated loads and isomorphic shifts, but have
>>>> only enough slots to do a reasonable job on a Gold.
>>>>
>>>> Try it on my66: input is an array of request bit-sizes, an input array
>>>> of bits, an output array of words, and a count. Unpack the consecutive
>>>> bit-size fields from the bits into the words.
>>>>
>>>> Have fun.
>>> <
>>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
>>> <
>>> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
>>> {
>>> uint64_t len,
>>> bit=0,
>>> word=0,
>>> extract,
>>> container1 = packed[0],
>>> container2 = packed[1];
>>>
>>> for( unsigned int i = 0; i < count; i++ )
>>> {
>>> len = size[i];
>>> extract = ( len << 32 ) | ( bit & 0x3F );
>>> bit += len;
>>> if( word != bit >> 6 )
>>> {
>>> container1 = container2;
>>> container2 = packed[++word];
>>> }
>>> unpacked[i] = {container2, container1} >> extract;
>>> }
>>> }
>> Perhaps I'm misreading your double right shift, but doesn't the second
>> no-reload extraction contain bits from the first? You aren't updating
>> the containers with a mask.
> <
> That is correct. I am leaving the containers in memory format, and extracting
> bit-fields from the pair of containers. When it is time to advance the pair of
> containers, I copy the second to the first and load a new second (Little Endian
> Order).
> <
> Note that while I use a shift operator (>>); I am performing a bit field extract
> because bits<37:32> of the shift count operand contain the size of the field
> to be extracted. This is non-portable--but how My 66000 works and how the
> industrious programmer can access extract without leaving C. AND you ask
> how this could be programmed in my66K (wrong spelling BTW).
> <
> Essentially, I keep track of the lower bit position of the extracted fields in
> two (2) counters {word and bit} and paste in the length of each field on a
> per loop basis.
>

Ah - I see. Whereas I would do unpacked[i] = extract(container2,
container1, bit, len); saves a shift, an and and an or, but uses two slots.

> loop:
> LDUB R10,[R1+R9]
> ADD R5,R5,R10
> AND R11,R5,#63
> SL R12,R10,#32
> OR R11,R11,R12
> SR R12,R6,#6
> CMP R11,R6,R12
> PEQ R11,{111}
> ADD R6,R6,#1
> MOV R7,R8
> LDD R8,[R2+R6<<3]
> CARRY R8,{{I}}
> SL R12,R7,R11
> STD R12,[R3+R9<<3]
> ADD R9,R9,#1
> CMP R11,R9,R4
> BLT R11,loop
> RET

There's still this `PEQ` predication which seems to lengthen the critical path
significantly, whereas ideally this "load next word" should be a kind of
"background task" that runs in parallel and is not in the critical path
(as long as it's fast enough).

Stefan

On Thursday, January 13, 2022 at 6:30:20 PM UTC-6, Stefan Monnier wrote:
> > loop:
> > LDUB R10,[R1+R9]
> > ADD R5,R5,R10
> > AND R11,R5,#63
> > SL R12,R10,#32
> > OR R11,R11,R12
> > SR R12,R6,#6
> > CMP R11,R6,R12
> > PEQ R11,{111}
> > ADD R6,R6,#1
> > MOV R7,R8
> > LDD R8,[R2+R6<<3]
> > CARRY R8,{{I}}
> > SL R12,R7,R11
> > STD R12,[R3+R9<<3]
> > ADD R9,R9,#1
> > CMP R11,R9,R4
> > BLT R11,loop
> > RET
> There's still this `PEQ` predication which seems to lengthen the critical path
> significantly, whereas ideally this "load next word" should be a kind of
> "background task" that runs in parallel and is not in the critical path
> (as long as it's fast enough).
<
Note: when doing things like Huffman decoding, most of the extractions
are small fields, and with 64-bit registers, you get a significant number
of extractions per container--maybe 12-16 extractions per container.
<
If you want, you can load both containers continuously and get rid of the
if-statement--this gives a more constant time version. Due to cache hit rates
on continuously accessed data, it might even be faster (but at higher power).
<
But, still: the predication still uses constant time FETCH-DECODE. Predication
always inserts the instructions into the instruction stream, and then cancels
them selectively. Predication is present to avoid disturbing the F-D process
making use of the vast momentum this process contains.
>
>
> Stefan

On Thursday, January 13, 2022 at 6:02:39 PM UTC-6, Ivan Godard wrote:
> On 1/13/2022 2:37 PM, MitchAlsup wrote:
> > On Thursday, January 13, 2022 at 4:18:43 PM UTC-6, Ivan Godard wrote:
> >> On 1/13/2022 12:23 PM, MitchAlsup wrote:
> >>> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> >>>> On 1/13/2022 7:54 AM, MitchAlsup wrote:
> >>>
> >>>> What's wrong is the need to conditionally refill and then merge the
> >>>> loaded value into the shift pair. The condition is totally
> >>>> unpredictable, so you get a miss every <word size>/<average request
> >>>> size> cycles. We have predicated loads and isomorphic shifts, but have
> >>>> only enough slots to do a reasonable job on a Gold.
> >>>>
> >>>> Try it on my66: input is an array of request bit-sizes, an input array
> >>>> of bits, an output array of words, and a count. Unpack the consecutive
> >>>> bit-size fields from the bits into the words.
> >>>>
> >>>> Have fun.
> >>> <
> >>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
> >>> <
> >>> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> >>> {
> >>> uint64_t len,
> >>> bit=0,
> >>> word=0,
> >>> extract,
> >>> container1 = packed[0],
> >>> container2 = packed[1];
> >>>
> >>> for( unsigned int i = 0; i < count; i++ )
> >>> {
> >>> len = size[i];
> >>> extract = ( len << 32 ) | ( bit & 0x3F );
> >>> bit += len;
> >>> if( word != bit >> 6 )
> >>> {
> >>> container1 = container2;
> >>> container2 = packed[++word];
> >>> }
> >>> unpacked[i] = {container2, container1} >> extract;
> >>> }
> >>> }
> >> Perhaps I'm misreading your double right shift, but doesn't the second
> >> no-reload extraction contain bits from the first? You aren't updating
> >> the containers with a mask.
> > <
> > That is correct. I am leaving the containers in memory format, and extracting
> > bit-fields from the pair of containers. When it is time to advance the pair of
> > containers, I copy the second to the first and load a new second (Little Endian
> > Order).
> > <
> > Note that while I use a shift operator (>>); I am performing a bit field extract
> > because bits<37:32> of the shift count operand contain the size of the field
> > to be extracted. This is non-portable--but how My 66000 works and how the
> > industrious programmer can access extract without leaving C. AND you ask
> > how this could be programmed in my66K (wrong spelling BTW).
> > <
> > Essentially, I keep track of the lower bit position of the extracted fields in
> > two (2) counters {word and bit} and paste in the length of each field on a
> > per loop basis.
> >
> Ah - I see. Whereas I would do unpacked[i] = extract(container2,
> container1, bit, len); saves a shift, an and and an or, but uses two slots.
<
I would argue the an extract IS a shift. But I can agree having to combine
both offset and length into a single container is not as efficient as if there
were enough register ports to do it as 1 instruction.

On Thursday, January 13, 2022 at 6:41:05 PM UTC-6, MitchAlsup wrote:
> On Thursday, January 13, 2022 at 6:02:39 PM UTC-6, Ivan Godard wrote:
> > On 1/13/2022 2:37 PM, MitchAlsup wrote:
> > >>>>
> > >>>> Try it on my66: input is an array of request bit-sizes, an input array
> > >>>> of bits, an output array of words, and a count. Unpack the consecutive
> > >>>> bit-size fields from the bits into the words.
> > >>>>
> > >>>> Have fun.
> > >>> <
> > >>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
> > >>>
This one puts the work into the container update, but requires 2 more registers.
<
void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
{ uint64_t len,
bit=0,
word=0,
extract,
mask,
container1 = packed[0],
container2 = packed[1];

for( unsigned int i = 0; i < count; i++ )
{
len = size[i];
mask = ~0u << len;
unpacked[i] = container1 & ~mask;
bit += len;
{ container2, container1 } >>= len; // this takes another register write port.

if( bit >> 6 )
{
container2 = packed[++word] ;
container1 |= container2 << (64-(bit&63)) // more background arithmetic
container 2 = container2 >> (bits&63);
}
}
} <
The cruft n the update looks to contain more arithmetic than the other way,
but might be faster. (MIGHT).

Thomas Koenig wrote:
> Ivan Godard <ivan@millcomputing.com> schrieb:
>
>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>> number of bits off the front of a bit stream, advancing the stream; word
>> boundaries are not significant. The problem is that HW provides word
>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>> is the same as mapping a line stream into a (VL) instruction stream in
>> the decoder's instruction buffer, but how to represent that in an ISA?
>
> The same way that a vector instruction would be represented?
>
> Vectors could be made to operate on sub-word quantities such as bytes,
> with microarchitectural SIMD underneath.
>
> I have to confess I do not know much of how compression and
> decompression algorithms work. What are the operations that need
> to be done with the chunk of bits that is grabbed?
>
That varies a _lot_! Absolute worst case in my experience is the CABAC
option for h264: Content-Adaptive-Binary-Arithmetic-Coding

Here you normally extract single bits from the input stream, then you
immediately branch on the value of that bit (by definition completely
unpredictable, right?) to two separate code paths that really cannot be
combined into a single branchless/predicated stream.

More sw-optimized algorithms/codecs, like LZ4, will make sure that
tokens are much easier to locate and then immediately usable inline
instead of having to branch away. LZ4 additionally makes life very easy
for a branch predictor by always alternating immediate data and
back-references to stuff that has already been decoded.

For that h264 BlueRay decompressor, the alternative (CATL afair?)
encoding needs a few percent more bandwidth but it is nearly an order of
magnitude easier to decode in sw.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, January 13, 2022 at 4:18:43 PM UTC-6, Ivan Godard wrote:
>> On 1/13/2022 12:23 PM, MitchAlsup wrote:
>>> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
>>>> On 1/13/2022 7:54 AM, MitchAlsup wrote:
>>>
>>>> What's wrong is the need to conditionally refill and then merge the
>>>> loaded value into the shift pair. The condition is totally
>>>> unpredictable, so you get a miss every <word size>/<average request
>>>> size> cycles. We have predicated loads and isomorphic shifts, but have
>>>> only enough slots to do a reasonable job on a Gold.
>>>>
>>>> Try it on my66: input is an array of request bit-sizes, an input array
>>>> of bits, an output array of words, and a count. Unpack the consecutive
>>>> bit-size fields from the bits into the words.
>>>>
>>>> Have fun.
>>> <
>>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
>>> <
>>> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
>>> {
>>> uint64_t len,
>>> bit=0,
>>> word=0,
>>> extract,
>>> container1 = packed[0],
>>> container2 = packed[1];
>>>
>>> for( unsigned int i = 0; i < count; i++ )
>>> {
>>> len = size[i];
>>> extract = ( len << 32 ) | ( bit & 0x3F );
>>> bit += len;
>>> if( word != bit >> 6 )
>>> {
>>> container1 = container2;
>>> container2 = packed[++word];
>>> }
>>> unpacked[i] = {container2, container1} >> extract;
>>> }
>>> }
>> Perhaps I'm misreading your double right shift, but doesn't the second
>> no-reload extraction contain bits from the first? You aren't updating
>> the containers with a mask.
> <
> That is correct. I am leaving the containers in memory format, and extracting
> bit-fields from the pair of containers. When it is time to advance the pair of
> containers, I copy the second to the first and load a new second (Little Endian
> Order).
> <
> Note that while I use a shift operator (>>); I am performing a bit field extract
> because bits<37:32> of the shift count operand contain the size of the field
> to be extracted. This is non-portable--but how My 66000 works and how the
> industrious programmer can access extract without leaving C. AND you ask
> how this could be programmed in my66K (wrong spelling BTW).
> <
> Essentially, I keep track of the lower bit position of the extracted fields in
> two (2) counters {word and bit} and paste in the length of each field on a
> per loop basis.
>

Essentially you are using exactly the same algorithm as I posted for
Huffmann decoding, except you get to write a branch around the reload
which the compiler can then turn into a predicated shadow block instead.

It might be possible to abuse the shift masking on x86 with a pair of
64-bit regs and SHRD, skipping the need to mask the bit position index:

mov rax,r8 ;; The buffer is 128 bits in R9:R8
shrd rax,r9,cl ;; Full bit count in RCX
and al,511 ;; Alternatively use a bitmask table
stosb ;; Save the token or do something with it
add rcx,9
mov rsi,rcx ;; Refill the full 128 bits here
shr rsi,6
mov r8,input[rsi]
mov r9,input[rsi+8]

Nope, this is almost certainly worse. :-(

With a full 128-bit buffer, it is faster to branch around the refill
unless it is actually needed.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Thursday, January 13, 2022 at 6:41:05 PM UTC-6, MitchAlsup wrote:
>> On Thursday, January 13, 2022 at 6:02:39 PM UTC-6, Ivan Godard wrote:
>>> On 1/13/2022 2:37 PM, MitchAlsup wrote:
>>>>>>>
>>>>>>> Try it on my66: input is an array of request bit-sizes, an input array
>>>>>>> of bits, an output array of words, and a count. Unpack the consecutive
>>>>>>> bit-size fields from the bits into the words.
>>>>>>>
>>>>>>> Have fun.
>>>>>> <
>>>>>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
>>>>>>
> This one puts the work into the container update, but requires 2 more registers.
> <
> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> {
> uint64_t len,
> bit=0,
> word=0,
> extract,
> mask,
> container1 = packed[0],
> container2 = packed[1];
>
> for( unsigned int i = 0; i < count; i++ )
> {
> len = size[i];
> mask = ~0u << len;
> unpacked[i] = container1 & ~mask;
> bit += len;
> { container2, container1 } >>= len; // this takes another register write port.
>
> if( bit >> 6 )
> {
> container2 = packed[++word] ;
> container1 |= container2 << (64-(bit&63)) // more background arithmetic
> container 2 = container2 >> (bits&63);
> }
> }
> }
> <
> The cruft n the update looks to contain more arithmetic than the other way,
> but might be faster. (MIGHT).
>

At this point, with typically small tokens, so (as you noted) lots of
them in a 64-bit register, it is better (in my experience) to actually
branch past the refill.

Don't you need a "bit &= 63" inside the refill, to bring it back down
under 64? Otherwise you'll repeat the block on every iteration?

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

On Friday, January 14, 2022 at 1:55:55 AM UTC-6, Terje Mathisen wrote:
> MitchAlsup wrote:
> > On Thursday, January 13, 2022 at 6:41:05 PM UTC-6, MitchAlsup wrote:
> >> On Thursday, January 13, 2022 at 6:02:39 PM UTC-6, Ivan Godard wrote:
> >>> On 1/13/2022 2:37 PM, MitchAlsup wrote:
> >>>>>>>
> >>>>>>> Try it on my66: input is an array of request bit-sizes, an input array
> >>>>>>> of bits, an output array of words, and a count. Unpack the consecutive
> >>>>>>> bit-size fields from the bits into the words.
> >>>>>>>
> >>>>>>> Have fun.
> >>>>>> <
> >>>>>> Minor update: had to move a unit of arithmetic so the first field is performed properly.
> >>>>>>
> > This one puts the work into the container update, but requires 2 more registers.
> > <
> > void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> > {
> > uint64_t len,
> > bit=0,
> > word=0,
> > extract,
> > mask,
> > container1 = packed[0],
> > container2 = packed[1];
> >
> > for( unsigned int i = 0; i < count; i++ )
> > {
> > len = size[i];
> > mask = ~0u << len;
> > unpacked[i] = container1 & ~mask;
> > bit += len;
> > { container2, container1 } >>= len; // this takes another register write port.
> >
> > if( bit >> 6 )
> > {
> > container2 = packed[++word] ;
> > container1 |= container2 << (64-(bit&63)) // more background arithmetic
> > container 2 = container2 >> (bits&63);
> > }
> > }
> > }
> > <
> > The cruft n the update looks to contain more arithmetic than the other way,
> > but might be faster. (MIGHT).
> >
> At this point, with typically small tokens, so (as you noted) lots of
> them in a 64-bit register, it is better (in my experience) to actually
> branch past the refill.
>
> Don't you need a "bit &= 63" inside the refill, to bring it back down
> under 64? Otherwise you'll repeat the block on every iteration?
<
The shift-count bits not being used ARE checked for significance, and raise
an exception if present. So, yes, I did this to myself. Although it can be
disabled, but I expect that some people wanting to do decoding will want
some kind of security and protection from out of domain values.
<
> Terje
>
> --
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

MitchAlsup wrote:
> On Friday, January 14, 2022 at 1:55:55 AM UTC-6, Terje Mathisen wrote:
>>
>> Don't you need a "bit &= 63" inside the refill, to bring it back down
>> under 64? Otherwise you'll repeat the block on every iteration?
> <
> The shift-count bits not being used ARE checked for significance, and raise
> an exception if present. So, yes, I did this to myself. Although it can be
> disabled, but I expect that some people wanting to do decoding will want
> some kind of security and protection from out of domain values.

My 66000 INS Insert Bitfield instruction could merge the shift
field width into the offset and chop off any high order width bits.
However my copy of the instruction manual doesn't show INS accepting
immediate w and o counts as other bitfield instructions, just register.

If DST reg was srcDst then SRC3 register wouldn't be needed
and it could have a 12-bit immediate w and o like others.

Also a CARRY with INS could allow inserting into a field
straddling two registers.

This would allow "INS rShiftCtrl,rNewWidth,6,32" to overwrite the
width field at offset 32 in rShiftCtrl with a new 6 bit width.

On Friday, January 14, 2022 at 2:14:07 PM UTC-6, EricP wrote:
> MitchAlsup wrote:
> > On Friday, January 14, 2022 at 1:55:55 AM UTC-6, Terje Mathisen wrote:
> >>
> >> Don't you need a "bit &= 63" inside the refill, to bring it back down
> >> under 64? Otherwise you'll repeat the block on every iteration?
> > <
> > The shift-count bits not being used ARE checked for significance, and raise
> > an exception if present. So, yes, I did this to myself. Although it can be
> > disabled, but I expect that some people wanting to do decoding will want
> > some kind of security and protection from out of domain values.
<
> My 66000 INS Insert Bitfield instruction could merge the shift
> field width into the offset and chop off any high order width bits.
> However my copy of the instruction manual doesn't show INS accepting
> immediate w and o counts as other bitfield instructions, just register.
<
Table 14: 3-operand Constant Specification
The above table shows when {I, S1, S2} = 0b111 that the shift count (Rs2)
constant is provided by a 64-bit immediate. These tables work across the
instruction groups to provide for the need (that is not just for FP, but for
any instructions in the group.)
<
Whether I should put another INS instruction with access to the 12-bit shift
immediates is another discussion; there is room.
>
> If DST reg was srcDst then SRC3 register wouldn't be needed
> and it could have a 12-bit immediate w and o like others.
<
But nothing else in the ISA would follow this self-modifying-register rule.
>
> Also a CARRY with INS could allow inserting into a field
> straddling two registers.
<
Perhaps.
>
> This would allow "INS rShiftCtrl,rNewWidth,6,32" to overwrite the
> width field at offset 32 in rShiftCtrl with a new 6 bit width.
<
Since the location is so fixed (bits<37:32>) one could place a constant in
a register (immed = <6:32>) and use this to insert len into the proper position.
One could also use the 64-bit immediate, and this might take 1 instruction
out of the loop.

On Thursday, January 13, 2022 at 11:53:45 AM UTC-6, MitchAlsup wrote:
> On Thursday, January 13, 2022 at 10:20:39 AM UTC-6, Ivan Godard wrote:
> > On 1/13/2022 7:54 AM, MitchAlsup wrote:
> > > On Thursday, January 13, 2022 at 6:07:29 AM UTC-6, Terje Mathisen wrote:
> > >> Ivan Godard wrote:
> > >>> On 1/12/2022 2:46 PM, MitchAlsup wrote:
> > >>>> On Wednesday, January 12, 2022 at 4:24:36 PM UTC-6, Ivan Godard wrote:
> > >>>>> On 1/12/2022 1:24 PM, MitchAlsup wrote:
> > >>>>>> On Monday, January 10, 2022 at 11:36:01 AM UTC-6, Quadibloc wrote:
> > >>>>>>> On Saturday, January 8, 2022 at 6:16:14 PM UTC-7, MitchAlsup wrote:
> > >>>>>>>
> > >>>>>>>> So, what does (13 << -7) mean ?
> > >>>>>>> From the replies, I see that this is a completely different
> > >>>>>>> can of worms. I would tend to favor the VAX interpretation,
> > >>>>>>> but it's unclear to me that it would be worth the extra
> > >>>>>>> run-time overhead that it might imply.
> > >>>>>> <
> > >>>>>> The VAX interpretation does not allow for shifts to be used as
> > >>>>>> bit-manipulation instructions (extract signed and unsigned).
> > >>>> <
> > >>>>> That turns into a rotate and a shft right. But isn't that what a
> > >>>>> hardware EXTR is going to do anyway?
> > >>>> <
> > >>>> Technically an extract is:
> > >>>> <
> > >>>> r = ((c << (containerWidth - fieldWidth - offset)) >>
> > >>>> (containerWidth-fieldWidth));
> > >>>> <
> > >>>> However, what we do in HW is:
> > >>>> <
> > >>>> m = tableM[fieldWidth]; // mask m:: often done
> > >>>> with table
> > >>>> s = ~0u << (fieldWidth+offset); // sign extension bits ::
> > >>>> often done with table
> > >>>> t = (c >> offset) & m | ( signed || (c & ( 1 <<
> > >>>> (fieldWidth+offset)) ? s : 0);
> > >>>> <
> > >>>> as this uses 1 shifter and either tables or greater-than decoders.
> > >>>> <
> > >>>> But the part I was hinting at is that we have a large container for
> > >>>> this shift
> > >>>> count and we need only a few bits on one end. So, in My 66000, the
> > >>>> upper ½
> > >>>> of the container is allowed to contain a value 0..64 (where both 0 and 64
> > >>>> mean 64-bit field width).
> > >>>> <
> > >>>> Done this way, shifts are degenerate subsets of EXT.
> > >>>> <
> > >>>> If you use the sign bit<63> to control shift direction, you probably
> > >>>> should not
> > >>>> be using bits<37:32> as the field width because pasting the fieldWidth
> > >>>> into
> > >>>> such a container is simply harder.
> > >>>> <
> > >>>> I learned the hard way about placing both containers too close together
> > >>>> in the Mc 88100.
> > >>>
> > >>> Hmm. So the container is a field descriptor. But it's not actually a
> > >>> bitRow, because it can't cross word boundaries - more like a PDP-10 PLT
> > >>> IIRC. Gives you some encoding entropy, but not actually any new
> > >>> semantic, and you have to build the descriptor, which you avoid when
> > >>> offset and width are separate arguments.
> > >>>
> > >>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
> > >>> number of bits off the front of a bit stream, advancing the stream; word
> > >>> boundaries are not significant. The problem is that HW provides word
> > >>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
> > >>> is the same as mapping a line stream into a (VL) instruction stream in
> > >>> the decoder's instruction buffer, but how to represent that in an ISA?
> > >> We did use to have something like that back in the PDP days with the
> > >> variable-sized load byte opcode that would automatically step forward to
> > >> the next work if needed.
> > >>
> > >> Today we would need a separate hw mechanism for that bitstream buffer,
> > >> and probably a filling mechanism which either would need to be
> > >> hardware-only or possibly a FILL_IF_ROOM target,offs,[src] opcode that
> > >> would load the next (8/16/32 bits into the target register at offs bit
> > >> offset, updating the OFFS reg and SRC pointer, but only if there was
> > >> room, otherwise it is a NOP. The main problem is the need to update all
> > >> three register operands. :-(
> > >>
> > >> Having it would however make it far easier to handle arbitrary bit
> > >> streams, avoiding the current need for branchy code.
> > > <
> > > What is wrong with having a container 2× as large as the largest bit-field
> > > then use a shift-double to position the bits at an appropriate
> > > place for extraction and then decoding/encoding.
> > What's wrong is the need to conditionally refill and then merge the
> > loaded value into the shift pair. The condition is totally
> > unpredictable, so you get a miss every <word size>/<average request
> > size> cycles. We have predicated loads and isomorphic shifts, but have
> > only enough slots to do a reasonable job on a Gold.
> >
> > Try it on my66: input is an array of request bit-sizes, an input array
> > of bits, an output array of words, and a count. Unpack the consecutive
> > bit-size fields from the bits into the words.
> >
> > Have fun.
> <
> I came up with this in 5 minutes::
> This assumes the input bit-length selector is an vector of characters and that the
> chars contain values from {1..64}
> <
> void unpack( uchar_t size[], uint64_t packed[], uint64_t unpacked[], uint64_t count )
> {
> uint64_t len,
> bit=0,
> word=0,
> extract,
> container1 = packed[0],
> container2 = packed[1];
>
> for( unsigned int i = 0; i < count; i++ )
> {
> len = size[i];
> bit += len;
> extract = ( len << 32 ) | ( bit & 0x3F );
> if( word != bit >> 6 )
> {
> container1 = container2;
> container2 = packed[++word];
> }
> unpacked[i] = {container2, container1} >> extract;
> }
> }
> <
> This translates into pretty nice My 66000 ISA:
> <
> ENTRY unpack
> unpack:
> MOV R5,#0
> MOV R6,#0
> LDD R7,[R2]
> LDD R8,[R2+8]
> MOV R9,#0
> loop:
> LDUB R10,[R1+R9]
> ADD R5,R5,R10
> AND R11,R5,#63
> SL R12,R10,#32
> OR R11,R11,R12
> SR R12,R6,#6
> CMP R11,R6,R12
> PEQ R11,{111}
> ADD R6,R6,#1
> MOV R7,R8
> LDD R8,[R2+R6<<3]
> CARRY R8,{{I}}
> SL R12,R7,R11
<
The above should be an SR (shift right) instruction.
<
> STD R12,[R3+R9<<3]
> ADD R9,R9,#1
> CMP R11,R9,R4
> BLT R11,loop
> RET
> <
> Well at least straightforwardly.

On 1/14/2022 12:28 PM, MitchAlsup wrote:
> On Friday, January 14, 2022 at 2:14:07 PM UTC-6, EricP wrote:
>> MitchAlsup wrote:
>>> On Friday, January 14, 2022 at 1:55:55 AM UTC-6, Terje Mathisen wrote:
>>>>
>>>> Don't you need a "bit &= 63" inside the refill, to bring it back down
>>>> under 64? Otherwise you'll repeat the block on every iteration?
>>> <
>>> The shift-count bits not being used ARE checked for significance, and raise
>>> an exception if present. So, yes, I did this to myself. Although it can be
>>> disabled, but I expect that some people wanting to do decoding will want
>>> some kind of security and protection from out of domain values.
> <
>> My 66000 INS Insert Bitfield instruction could merge the shift
>> field width into the offset and chop off any high order width bits.
>> However my copy of the instruction manual doesn't show INS accepting
>> immediate w and o counts as other bitfield instructions, just register.
> <
> Table 14: 3-operand Constant Specification
> The above table shows when {I, S1, S2} = 0b111 that the shift count (Rs2)
> constant is provided by a 64-bit immediate. These tables work across the
> instruction groups to provide for the need (that is not just for FP, but for
> any instructions in the group.)
> <
> Whether I should put another INS instruction with access to the 12-bit shift
> immediates is another discussion; there is room.
>>
>> If DST reg was srcDst then SRC3 register wouldn't be needed
>> and it could have a 12-bit immediate w and o like others.
> <
> But nothing else in the ISA would follow this self-modifying-register rule.
>>
>> Also a CARRY with INS could allow inserting into a field
>> straddling two registers.
> <
> Perhaps.
>>
>> This would allow "INS rShiftCtrl,rNewWidth,6,32" to overwrite the
>> width field at offset 32 in rShiftCtrl with a new 6 bit width.
> <
> Since the location is so fixed (bits<37:32>) one could place a constant in
> a register (immed = <6:32>) and use this to insert len into the proper position.
> One could also use the 64-bit immediate, and this might take 1 instruction
> out of the loop.

Doesn't the use of combined extract arguments preclude use by your
vector facility?

Also, how does the vector interact with the projected predicate?

On Friday, January 14, 2022 at 7:07:49 PM UTC-6, Ivan Godard wrote:
> On 1/14/2022 12:28 PM, MitchAlsup wrote:
> > On Friday, January 14, 2022 at 2:14:07 PM UTC-6, EricP wrote:
> >> MitchAlsup wrote:
> >>> On Friday, January 14, 2022 at 1:55:55 AM UTC-6, Terje Mathisen wrote:
> >>>>
> >>>> Don't you need a "bit &= 63" inside the refill, to bring it back down
> >>>> under 64? Otherwise you'll repeat the block on every iteration?
> >>> <
> >>> The shift-count bits not being used ARE checked for significance, and raise
> >>> an exception if present. So, yes, I did this to myself. Although it can be
> >>> disabled, but I expect that some people wanting to do decoding will want
> >>> some kind of security and protection from out of domain values.
> > <
> >> My 66000 INS Insert Bitfield instruction could merge the shift
> >> field width into the offset and chop off any high order width bits.
> >> However my copy of the instruction manual doesn't show INS accepting
> >> immediate w and o counts as other bitfield instructions, just register.
> > <
> > Table 14: 3-operand Constant Specification
> > The above table shows when {I, S1, S2} = 0b111 that the shift count (Rs2)
> > constant is provided by a 64-bit immediate. These tables work across the
> > instruction groups to provide for the need (that is not just for FP, but for
> > any instructions in the group.)
> > <
> > Whether I should put another INS instruction with access to the 12-bit shift
> > immediates is another discussion; there is room.
> >>
> >> If DST reg was srcDst then SRC3 register wouldn't be needed
> >> and it could have a 12-bit immediate w and o like others.
> > <
> > But nothing else in the ISA would follow this self-modifying-register rule.
> >>
> >> Also a CARRY with INS could allow inserting into a field
> >> straddling two registers.
> > <
> > Perhaps.
> >>
> >> This would allow "INS rShiftCtrl,rNewWidth,6,32" to overwrite the
> >> width field at offset 32 in rShiftCtrl with a new 6 bit width.
> > <
> > Since the location is so fixed (bits<37:32>) one could place a constant in
> > a register (immed = <6:32>) and use this to insert len into the proper position.
> > One could also use the 64-bit immediate, and this might take 1 instruction
> > out of the loop.
<
> Doesn't the use of combined extract arguments preclude use by your
> vector facility?
<
No
>
> Also, how does the vector interact with the projected predicate?
<
The data dependencies that permeate the predicated block and cause the
loop to take more cycles than the required arithmetic requires. That is: the
data dependencies within the predicated block are themselves dependent
on the predicating condition.
<
But what you are getting at is to reformulate the loop so that as long as the
containers are not fully consumed, stay in one loop. Then when one needs
to switch containers, exit the vectorized loop, update the containers and
repeat until done.

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Thomas Koenig wrote:
>> Ivan Godard <ivan@millcomputing.com> schrieb:
>>
>>> Where ISAs really fall down is parsing a bit stream: grab a dynamic
>>> number of bits off the front of a bit stream, advancing the stream; word
>>> boundaries are not significant. The problem is that HW provides word
>>> streams (loop/load) and mapping that to a bit stream is nasty. The logic
>>> is the same as mapping a line stream into a (VL) instruction stream in
>>> the decoder's instruction buffer, but how to represent that in an ISA?
>>
>> The same way that a vector instruction would be represented?
>>
>> Vectors could be made to operate on sub-word quantities such as bytes,
>> with microarchitectural SIMD underneath.
>>
>> I have to confess I do not know much of how compression and
>> decompression algorithms work. What are the operations that need
>> to be done with the chunk of bits that is grabbed?
>>
> That varies a _lot_! Absolute worst case in my experience is the CABAC
> option for h264: Content-Adaptive-Binary-Arithmetic-Coding
>
> Here you normally extract single bits from the input stream, then you
> immediately branch on the value of that bit (by definition completely
> unpredictable, right?) to two separate code paths that really cannot be
> combined into a single branchless/predicated stream.

Interesting. You can do it in hardware in parallel, then select
the result. I would assume that the workloads of the two branches
are roughly the same?

A general purpose CPU could do something similar. A superscalar
in-order architecture could distribute the work between its
pipelines. If the ISA has a way to specify separate execution
units, so that (in SSA form)

if (condition) {
foo_1 = some work;
}
else {
foo_2 = some other work;
}
foo = PHI (foo_1, foo_2);

this could be implemented efficiently even on a superscalar
in-order machine.

I know this can be done with Mitch's shadow modifier for a limited
number of instructions, and I also suspect that I am just describing
a feature of the Mill.