eval.tex

\chapter{Evaluation}

This chapter contains a collection of short code snippets and algorithms using
the XBitmanip extension for evaluation purposes. For the sake of simplicity we
assume RV32 for most examples in this chapter.

Most assembler routines in this chapter are written as if they were ABI functions,
i.e. arguments are passed in a0, a1,~\dots~and results are returned in a0. Registers
a0, a1,~\dots~are also used for spilling Registers t0, t1,~\dots~are used for
pre-computed masks to be used with {\tt bext}/{\tt bdep}.

Some of the assembler routines below can not or should not overwrite their
first argument. In those cases the arguments are passed in a1, a2,~\dots~and
results are returned in a0.

The main motivarion behind this chapter is to show that all the common bit
manipulation tasks can be performed in few instructions using XBitmanip. (In
many cases RV32I/RV64I instructions are already sufficient.) In most cases the
sequences are short enough to allow large cores to macro-op-fuse them into a
single instruction. For this reason we also focus on code snippets that do
not spill any registers, as this further simplifies macro-op fusion.

There likely will be a separate RISC-V standard for recommended sequences for
macro-op fusion. The macros listed here are merely for demonstrating that
suitable sequences exist. We do not advocate for any of those sequences to
become ``standard sequences'' for macro-op fusion.

\section{Bitfield extract}

Extracting a bit field of length {\tt len} at position {\tt pos} can be done using
two shift operations (or equivialently using the {\tt bfext} pseudo instruction, see
Section~\ref{bfext}).

\begin{verbatim}
  c.slli a0, (XLEN-pos-len)
  c.srli a0, (XLEN-len)
\end{verbatim}

The XBitfield {\tt bfxp} instruction (see Chapter~\ref{bfxp}) performs this operation
plus one more left shift and an OR operation in a single instruction.

\section{MIX/MUX pattern}
\label{mixmux}

A MIX pattern selects bits from {\tt a0} and {\tt a1} based on the bits in
the control word {\tt a2}.

\begin{verbatim}
  c.and a0, a2
  andc a1, a1, a2
  c.or a0, a1
\end{verbatim}

A MUX operation selects word {\tt a0} or {\tt a1} based on if the control
word {\tt a2} is zero or nonzero, without branching.

\begin{verbatim}
  snez a2, a2
  c.neg a2
  c.and a0, a2
  andc a1, a1, a2
  c.or a0, a1
\end{verbatim}

Or when {\tt a2} is already either 0 or 1:

\begin{verbatim}
  c.neg a2
  c.and a0, a2
  andc a1, a1, a2
  c.or a0, a1
\end{verbatim}

Alternatively, a core might fuse a conditional branch that just skips one
instruction with that instruction to form a fused conditional macro-op.

\section{Bit scanning and counting}

Counting leading ones:

\begin{verbatim}
  c.not a0
  clz a0, a0
\end{verbatim}

Counting trailing ones:

\begin{verbatim}
  c.not a0
  ctz a0, a0
\end{verbatim}

Counting bits cleared:

\begin{verbatim}
  c.not a0
  pcnt a0, a0
\end{verbatim}

(This is better than XLEN-pcnt because RISC-V has no ``reverse-subtract-immediate'' operation.)

Odd parity:

\begin{verbatim}
  pcnt a0, a0
  c.andi a0, 1
\end{verbatim}

Even parity:

\begin{verbatim}
  pcnt a0, a0
  c.addi a0, 1
  c.andi a0, 1
\end{verbatim}

(Using {\tt addi} here is better than using {\tt xori}, because there is
a compressed opcode for {\tt addi} but none for {\tt xori}.)

\section{Test, set, and clear individual bits}

Extracting bit N:

\begin{verbatim}
  c.srli a0, N
  c.andi a0, 1
\end{verbatim}

Branching on bit N set:

\begin{verbatim}
  c.slli a0, (XLEN-N-1)
  bltz a0, <bit_n_set>
\end{verbatim}

Branching on bit N clear:

\begin{verbatim}
  c.slli a0, (XLEN-N-1)
  bgez a0, <bit_n_clear>
\end{verbatim}

Setting bit N (note that this {\tt li} is only one instruction on RV32, except when N=11 which requires two instructions):

\begin{verbatim}
  li a1, (1 << N)
  c.or a0, a1
\end{verbatim}

Setting bit N without spilling:

\begin{verbatim}
  rori a0, a0, N
  ori a0, 1
  rori a0, a0, 32-N
\end{verbatim}

(Or simply ``{\tt ori a0, 1 << N}'' if N is sufficiently small.)

Clearing bit N (note that this {\tt li} is only one instruction on RV32, except when N=11 which requires two instructions):

\begin{verbatim}
  li a1, (1 << N)
  andc a0, a1
\end{verbatim}

Clearing bit N without spilling:

\begin{verbatim}
  rori a0, a0, N
  c.andi a0, -2
  rori a0, a0, XLEN-N
\end{verbatim}

(Or simply ``{\tt andi a0, $\sim$(1 << N)}'' if N is sufficiently small.)

Setting bit N to the value in {\tt a1} (assuming a1 already is either 0 or 1):

\begin{verbatim}
  rori a0, a0, N
  c.andi a0, -2
  c.or a0, a1
  rori a0, a0, 32-N
\end{verbatim}

\section{Funnel shifts}
\label{funnel}

A funnel shift takes two XLEN registers, concatenates them to a $2 \times \textrm{XLEN}$ word,
shifts that by a certain amount, then returns the lower half of the result
for a right shift and the upper half of the result for a left shift.

This can be very useful for processing a stream of bit data that is not
composed of units aligned to byte boundaries. (Especially when implemented
in a single instruction, it can also be useful for misaligned memcopy when
source and destination are not misaligned by the same offset.)

Performing a funnel right shift of {\tt a0} (LSB) and {\tt a1} (MSB) by the
shift amount specified in {\tt a2} (with $0 < \texttt{a2} < \textrm{XLEN}$):

\begin{verbatim}
  c.srl a0, a2
  c.neg a2
  c.sll a1, a2
  c.or a0, a1
\end{verbatim}

When the shift amount is a compile-time constant, then a 32-bit funnel shift can be
performed using two XBitfield {\tt bfxp} instructions (see Chapter~\ref{bfxp}):

\begin{verbatim}
  bfxp a0, a0, zero, N, 32-N, 0
  bfxp a0, a1, a0, 0, N, 32-N
\end{verbatim}

\section{Arbitrary bit permutations}

This section lists code snippets for computing arbitrary bit permutations that
are defined by data (as opposed to bit permutations that are known at compile
time and can likely be compiled into shift-and-mask operations and/or a few
instances of bext/bdep).

\subsection{Using butterfly operations}
\label{butterfly}

The following macro performs a stage-{\tt N} butterfly operation on the word in
{\tt a0} using the mask in {\tt a1}.

\begin{verbatim}
  grevi a2, a0, (1 << N)
  c.and a2, a1
  andc a0, a0, a1
  c.or a0, a2
\end{verbatim}

The bitmask in {\tt a1} must be preformatted correctly for the selected butterfly
stage. A butterfly operation only has a XLEN/2 wide control word. The following
macros format the mask assuming those XLEN/2 bits in the lower half of {\tt a1}
on entry (preformatted mask in {\tt a1} on exit):

\begin{verbatim}
bfly_msk_0:
  zip a1, a1
  slli a2, a1, 1
  c.or a1, a2

bfly_msk_1:
  zip2 a1, a1
  slli a2, a1, 2
  c.or a1, a2

bfly_msk_2:
  zip4 a1, a1
  slli a2, a1, 4
  c.or a1, a2

...
\end{verbatim}

A sequence of $2\cdot{}log_2(\textrm{XLEN})-1$ butterfly operations can perform any
arbitrary bit permutation (Bene{\v s} network):

\begin{verbatim}
  butterfly(LOG2_XLEN-1)
  butterfly(LOG2_XLEN-2)
  ...
  butterfly(0)
  ...
  butterfly(LOG2_XLEN-2)
  butterfly(LOG2_XLEN-1)
\end{verbatim}


Many permutations arising from real-world applications can be implemented
using shorter sequences. For example, any sheep-and-goats operation with either
the sheep or the goats bit reversed can be implemented in $log_2(\textrm{XLEN})$
butterfly operations.

Reversing a permutation implemented using butterfly operations is as simple as
reversing the order of butterfly operations.

% References
% http://www.princeton.edu/~rblee/PUpapers/xiao_spie00.pdf
% https://www.lirmm.fr/arith18/papers/hilewitz-PerformingBitManipulations.pdf
% https://pdfs.semanticscholar.org/bcd0/8fdccf3d5ab959fd81162bd811706ba1676a.pdf

\subsection{Using omega-flip networks}

The omega operation is a stage-0 butterfly preceeded by a zip operation:

\begin{verbatim}
  zip a0, a0
  grevi a2, a0, 1
  c.and a2, a1
  andc a0, a0, a1
  c.or a0, a2
\end{verbatim}

The flip operation is a stage-0 butterfly followed by an unzip operation:

\begin{verbatim}
  grevi a2, a0, 1
  c.and a2, a1
  andc a0, a0, a1
  c.or a0, a2
  unzip a0, a0
\end{verbatim}

A sequence of $log_2(\textrm{XLEN})$ omega operations followed by
$log_2(\textrm{XLEN})$ flip operations can implement any arbitrary 32 bit
permutation.

As for butterfly networks, permutations arising from real-world applications
can often be implemented using a shorter sequence.

% References
% https://ieeexplore.ieee.org/document/878264/
% https://www.princeton.edu/~rblee/ELE572Papers/lee_slideshotchips2002.pdf

\subsection{Using baseline networks}

Another way of implementing arbitrary 32 bit permutations is using a
baseline network followed by an inverse baseline network.

A baseline network is a sequence of $log_2(\textrm{XLEN})$ butterfly(0)
operations interleaved with unzip operations. For example, a 32-bit
baseline network:

\begin{verbatim}
  butterfly(0)
  unzip
  butterfly(0)
  unzip.h
  butterfly(0)
  unzip.b
  butterfly(0)
  unzip.n
  butterfly(0)
\end{verbatim}

An inverse baseline network is a sequence of $log_2(\textrm{XLEN})$ butterfly(0)
operations interleaved with zip operations. The order is opposite to the
order in a baseline network. For example, a 32-bit inverse baseline network:

\begin{verbatim}
  butterfly(0)
  zip.n
  butterfly(0)
  zip.b
  butterfly(0)
  zip.h
  butterfly(0)
  zip
  butterfly(0)
\end{verbatim}

A baseline network followed by an inverse baseline network can implement
any arbitrary bit permutation.

% References
% https://dl.acm.org/citation.cfm?id=1311797

\subsection{Using sheep-and-goats}

The Sheep-and-goats (SAG) operation is a common operation for bit permutations.
It moves all the bits selected by a mask (goats) to the LSB end of the word
and all the remaining bits (sheep) to the MSB end of the word, without changing
the order of sheep or goats.

The SAG operation can easily be performed using {\tt bext} (data in {\tt a0} and
mask in {\tt a1}):

\begin{verbatim}
  bext a2, a0, a1
  c.not a1
  bext a0, a0, a1
  pcnt a1, a1
  ror a0, a0, a1
  c.or a0, a2
\end{verbatim}

Any arbitrary bit permutation can be implemented in $log_2(\textrm{XLEN})$ SAG
operations.

{\it The Hacker's Delight} describes an optimized standard C implementation of
the SAG operation. Their algorithm takes 254 instructions (for 32 bit) or 340
instructions (for 64 bit) on their reference RISC instruction
set.~\cite[p.~152f,~162f]{Seander05}

% References
% Knuth
% Hackers Delight, Chapter 7-7

\section{Comparison with x86 Bit Manipulation ISAs}
\label{x86comp}

The following code snippets implement all instructions from the x86 bit manipulation
ISA extensions ABM, BMI1, BMI2, and TBM using RISC-V code that does not spill any
registers and thus could easily be implemented in a single instruction using macro-op
fusion. (Some of them simply map directly to instructions in this spec and so no
macro-op fusion is needed.) Note that shorter RISC-V code sequences are
sometimes possible if we allow spilling to temporary registers.

ABM added x86 encodings for POPCNT, LZCNT, and TZCNT.\footnote{Depending on if
you ask Intel or AMD you will get different opinion regarding whether LZCNT
and/or TZCNT are part of ABM or BMI1.} The difference between LZCNT and the
80386 instruction BSR, and between TZCNT and the 80386 instruction BSF, is that
the new instructions return the operand size when the input operand is zero,
while BSR and BSF were undefined in that case. The ABM instructions map 1:1 to
XBitmanip instructions. Table~\ref{abm-comp} lists ABM instructions and regular
x86 bit manipulation instructions.

\begin{table}[h]
\centering
\begin{tabular}{lrrl}
\multirow{2}{*}{x86 Instruction} & \multicolumn{2}{c}{Bytes} & \multirow{2}{*}{RISC-V Code} \\
& x86 & RV & \\
\hline
POPCNT       &   5 &  4 & {\tt pcnt a0, a0} \\
\hline
LZCNT / BSR  &   5 &  4 & {\tt clz a0, a0} \\
\hline
TZCNT / BSF  &   5 &  4 & {\tt ctz a0, a0} \\
\hline
BSWAP        &   3 &  4 & {\tt bswap} \\
\hline
ROL          &   4 &  4 & {\tt roli} \\
\hline
ROR          &   4 &  4 & {\tt rori} \\
\hline
BT           &   5 &  4 & {\tt c.srl a0, N} \\
             &     &    & {\tt c.andi a0, 1} \\
\hline
BTC          &   5 & 16 & {\tt rori a0, N} \\
             &     &    & {\tt andi a1, a0, 1} \\
             &     &    & {\tt xori a0, a0, 1} \\
             &     &    & {\tt rori a0, XLEN-N} \\
\hline
BTR          &   5 & 16 & {\tt rori a0, N} \\
             &     &    & {\tt andi a1, a0, 1} \\
             &     &    & {\tt andi a0, a0, -2} \\
             &     &    & {\tt rori a0, XLEN-N} \\
\hline
BTS          &   5 & 16 & {\tt rori a0, N} \\
             &     &    & {\tt andi a1, a0, 1} \\
             &     &    & {\tt ori a0, a0, 1} \\
             &     &    & {\tt rori a0, XLEN-N} \\
\end{tabular}
\caption{Comparison of x86+ABM with XBitmanip}
\label{abm-comp}
\end{table}

BMI1 adds some instructions for trailing bit manipulations, an add-complement instruction,
and a bit field extract instruction that expects the length and start position packed in one
register operand. Our version expects the length in a0, start position in a1, and source
value in a2. See Table~\ref{bmi1-comp}.

\begin{table}[h]
\centering
\begin{tabular}{lrrl}
\multirow{2}{*}{x86 Instruction} & \multicolumn{2}{c}{Bytes} & \multirow{2}{*}{RISC-V Code} \\
& x86 & RV & \\
\hline
ANDN    & 5 &  4 & {\tt andc a0, a2, a1} \\
\hline
BEXTR (regs)  & 5 & 12 & {\tt c.add a0, a1} \\
              &   &    & {\tt slo a0, zero, a0} \\
              &   &    & {\tt c.and a0, a2} \\
              &   &    & {\tt srl a0, a0, a1} \\
\hline
BLSI          & 5 &  6 & {\tt neg a0, a1} \\
              &   &    & {\tt c.and a0, a1} \\
\hline
BLSMSK        & 5 &  6 & {\tt addi a0, a1, -1} \\
              &   &    & {\tt c.xor a0, a1} \\
\hline
BLSR          & 5 &  6 & {\tt addi a0, a1, -1} \\
              &   &    & {\tt c.and a0, a1} \\
\end{tabular}
\caption{Comparison of x86 BMI1 with XBitmanip}
\label{bmi1-comp}
\end{table}

BMI2 adds a few \texttt{*X} isnstructions that just perform the indicated
operation without changing any flags. RISC-V does not use flags, so this
instructions trivially just map to their regular RISC-V counterparts. In
addition to those instructions, BMI2 adds bit extract and deposit instructions
and an instruction to clear high bits above a given bit index. See Table~\ref{bmi2-comp}.

\begin{table}[h]
\centering
\begin{tabular}{lrrl}
\multirow{2}{*}{x86 Instruction} & \multicolumn{2}{c}{Bytes} & \multirow{2}{*}{RISC-V Code} \\
& x86 & RV & \\
\hline
BZHI     & 5 &  6 & {\tt slo a0, zero, a2} \\
         &   &    & {\tt c.and a0, a1} \\
\hline
PDEP     & 5 &  4 & {\tt bdep} \\
\hline
PEXT     & 5 &  4 & {\tt bext} \\
\hline
MULX     & 5 &  4 & {\tt mul} \\
\hline
RORX     & 6 &  4 & {\tt rori} \\
\hline
SARX     & 5 &  4 & {\tt sra} \\
\hline
SHRX     & 5 &  4 & {\tt srl} \\
\hline
SHLX     & 5 &  4 & {\tt sll} \\
\end{tabular}
\caption{Comparison of x86 BMI2 with XBitmanip}
\label{bmi2-comp}
\end{table}

Finally, TBM was a short-lived x86 ISA extension introduced by AMD in
Piledriver processors, complementing the trailing bit manipulation instructions
from BMI1. See Table~\ref{tbm-comp}.

\begin{table}[h]
\centering
\begin{tabular}{lrrl}
\multirow{2}{*}{x86 Instruction} & \multicolumn{2}{c}{Bytes} & \multirow{2}{*}{RISC-V Code} \\
& x86 & RV & \\
\hline
BEXTR (imm)  & 7 &  4 & {\tt c.slli a0, (32-START-LEN)} \\
             &   &    & {\tt c.srli a0, (32-LEN)} \\
\hline
BLCFILL      & 5 &  6 & {\tt addi a0, a1, 1} \\
             &   &    & {\tt c.and a0, a1} \\
\hline
BLCI         & 5 &  8 & {\tt addi a0, a1, 1} \\
             &   &    & {\tt c.not a0} \\
             &   &    & {\tt c.or a0, a1} \\
\hline
BLCIC        & 5 & 10 & {\tt addi a0, a1, 1} \\
             &   &    & {\tt andc a0, a1, a0} \\
             &   &    & {\tt c.not a0} \\
\hline
BLCMSK       & 5 &  6 & {\tt addi a0, a1, 1} \\
             &   &    & {\tt c.xor a0, a1} \\
\hline
BLCS         & 5 &  6 & {\tt addi a0, a1, 1} \\
             &   &    & {\tt c.or a0, a1} \\
\hline
BLSFILL      & 5 &  6 & {\tt addi a0, a1, -1} \\
             &   &    & {\tt c.or a0, a1} \\
\hline
BLSIC        & 5 & 10 & {\tt addi a0, a1, -1} \\
             &   &    & {\tt andc a0, a1, a0} \\
             &   &    & {\tt c.not a0} \\
\hline
T1MSKC       & 5 & 10 & {\tt addi a0, a1, +1} \\
             &   &    & {\tt andc a0, a1, a0} \\
             &   &    & {\tt c.not a0} \\
\hline
T1MSK        & 5 &  8 & {\tt addi a0, a1, -1} \\
             &   &    & {\tt andc a0, a0, a1} \\
\end{tabular}
\caption{Comparison of x86 TBM with XBitmanip}
\label{tbm-comp}
\end{table}

\section{Comparison with RI5CY Bit Manipulation ISA}

The following section compares XBitmanip with the RI5CY bit manipulation
instructions as documented in~\cite{Ri5cy}. All RI5CY bit manipulation
instructions (or something very close to their behavior) can be emulated with
XBitmanip using 3 instructions or less.

\subsubsection{RI5CY Instructions {\tt p.extract}, {\tt p.extractu}, {\tt p.extractr}, and {\tt p.extractur}}

These four RI5CY instructions extract bit-fields. The non-{\tt u}-versions sign-extend
the extracted bit-field. This operations can be performed with two shift-immediate
operations. It even fits in a 32-bit word when using compressed instructions (requires
{\tt rd} $=$ {\tt rs}).

\begin{verbatim}
  p.extract rd, rs, len, pos:
    slli rd, rs, (XLEN-pos-len)
    srai rd, rd, (XLEN-len)

  p.extractu rd, rs, len, pos:
    slli rd, rs, (XLEN-pos-len)
    srli rd, rd, (XLEN-len)
\end{verbatim}

The {\tt r}-versions expect the bit-field size in bits 9:5 of the second source
register and the bit-field start in bits 4:0. Instead we use two registers,
$\texttt{rx} = XLEN-pos-len$ and $\texttt{ry} = XLEN-len$.

\begin{verbatim}
  p.extractr:
    sll rd, rs, rx
    sra rd, rd, ry

  p.extractur:
    sll rd, rs, rx
    srl rd, rd, ry
\end{verbatim}

Alternatively, instead of packing length and position into a register, we
can create a mask in a register and then use this mask with {\tt bext}. This
has the advantage over the {\tt sll}+{\tt srl} sequence that the mask only needs
to be generated once and can then be re-used many times, effectively implementing
{\tt p.extractur} in a single instruction.

\begin{verbatim}
  p.extractur:
    slo rMask, zero, rLen
    sll rMask, rMask, rPos
    bext rd, rs, rMask
\end{verbatim}

{\tt p.extractu} can be efficiently emulated with a single XBitfield {\tt bfxp}
instruction (see Chapter~\ref{bfxp}):

\begin{verbatim}
  p.extract rd, rs, len, pos:
    bfxp rd, rs, zero, pos, len, 0
\end{verbatim}

\subsubsection{RI5CY Instructions {\tt p.insert} and {\tt p.insertr}}

These instructions OR the destination register with the {\tt len} LSB bits
from the source register, shifted up by {\tt pos} bits. This can easily
be achieved using three instructions and a temporary register {\tt rt}:

\begin{verbatim}
  p.insert rd, rs, len, pos, rt:
    slli rt, rs, (XLEN-len)
    srli rt, rt, (XLEN-len-pos)
    or rd, rd, rt
\end{verbatim}

The {\tt r}-version of the instruction expects {\tt len} in bits 9:5 of the
second source register and {\tt pos} in bits 4:0. Instead we use two registers,
$\texttt{rx} = XLEN-pos-len$ and $\texttt{ry} = XLEN-len$.

\begin{verbatim}
  p.insertr:
    slli rt, rs, ry
    srli rt, rt, rx
    or rd, rd, rt
\end{verbatim}

Alternatively, instead of packing length and position into a register, we
can create a mask in a register and then use this mask with {\tt bdep}. This
has the advantage over the {\tt sll}+{\tt srl} sequence that the mask only needs
to be generated once and can then be re-used many times.

\begin{verbatim}
  p.extractur:
    slo rMask, zero, rLen
    sll rMask, rMask, rPos
    bdep rt, rs, rMask
    or rd, rd, rt
\end{verbatim}

{\tt p.insert} can be efficiently emulated with a single XBitfield {\tt bfxp}
instruction (see Chapter~\ref{bfxp}), if target region in {\tt rd} contains
only zeros ({\tt bfxp} clears the target region before performing the OR):

\begin{verbatim}
  p.insert rd, rs, len, pos:
    bfxp rd, rs, rd, 0, len, pos
\end{verbatim}

\subsubsection{RI5CY Instructions {\tt p.bclr} and {\tt p.bclrr}}

These instructions clear {\tt len} bits starting with bit {\tt pos}. Using a
temporary register {\tt rt}:

\begin{verbatim}
  p.bclr rd, rs, len, pos, rt:
    sloi rt, zero, len
    slli rt, rt, pos
    andc rd, rs, rt
\end{verbatim}

Or using two registers {\tt rLen} and {\tt rPos}:

\begin{verbatim}
  p.bclrr rd, rs, rLen, rPos, rt:
    slo rt, zero, rLen
    sll rt, rt, rPos
    andc rd, rs, rt
\end{verbatim}

If the mask in {\tt rt} can be pre-computed then a single {\tt andc} instruction
can emulate {\tt p.bclrr}, or a single {\tt and}/{\tt c.and} instruction if the
mask is already inverted.

Or using {\tt bfxp} with $\texttt{rd} = \texttt{rs}$ (see Chapter~\ref{bfxp}):

\begin{verbatim}
  p.bclr rd, len, pos:
    bfxp rd, zero, rd, 0, len, pos
\end{verbatim}

\subsubsection{RI5CY Instructions {\tt p.bset} and {\tt p.bsetr}}

These instructions set {\tt len} bits starting with bit {\tt pos}. They can be
implemented similar to {\tt p.bclr} and {\tt p.bclrr} by replacing {\tt andc}
with {\tt or}:

\begin{verbatim}
  p.bset rd, rs, len, pos, rt:
    sloi rt, zero, len
    slli rt, rt, pos
    or rd, rs, rt

  p.bsetr rd, rs, rLen, rPos, rt:
    slo rt, zero, rLen
    sll rt, rt, rPos
    or rd, rs, rt
\end{verbatim}

If the mask in {\tt rt} can be pre-computed then a single {\tt or}/{\tt c.or} instruction
can emulate {\tt p.bsetr}.

Or using {\tt bfxpc} with $\texttt{rd} = \texttt{rs}$ (see Chapter~\ref{bfxp}):

\begin{verbatim}
  p.bset rd, len, pos:
    bfxpc rd, zero, rd, 0, len, pos
\end{verbatim}

\subsubsection{RI5CY Instructions {\tt p.ff1}, {\tt p.cnt}, and {\tt p.ror}}

These instructions map directly to the XBitmanip instructions {\tt ctz}, {\tt pcnt}, and {\tt ror}.

\subsubsection{RI5CY Instructions {\tt p.fl1}}

This instruction returns the index of the last set bit in {\tt rs}. If {\tt rs} is 0, {\tt rd} will be 0.

Using the arguably more useful definition that the operation should return -1 when {\tt rs} is 0:

\begin{verbatim}
  p.fl1 rd, rs:
    clz rd, rs
    neg rd, rd
    addi rd, rd, 31
\end{verbatim}

Converting a -1 result to 0 to match the exact {\tt p.fl1} behavior:

\begin{verbatim}
    slt rt, rd, zero
    add rd, rd, rt
\end{verbatim}

\subsubsection{RI5CY Instructions {\tt p.clb}}

This instruction counts the number of consecutive 1s or 0s from MSB. If {\tt rs} is 0, {\tt rd} will be 0.

Using the arguably more useful definition that the operation should return XLEN when {\tt rs} is 0 or -1,
and assuming {\tt rd} $\ne$ {\tt rs1}:

\begin{verbatim}
  p.clb:
    srai rd, rs, XLEN-1
    xor rd, rd, rs
    clz rd, rd
\end{verbatim}

Simply add {\tt andi rd, rd, XLEN-1} if {\tt rd} should be 0 when {\tt rs} is 0 or -1.

\section{Mirroring and rotating bitboards}

Bitboards are 64-bit bitmasks that are used to represent part of the game state
in chess engines (and other board game AIs). The bits in the bitmask correspond
to squares on a $8 \times 8$ chess board:

\begin{verbatim}
 56 57 58 59 60 61 62 63
 48 49 50 51 52 53 54 55
 40 41 42 43 44 45 46 47
 32 33 34 35 36 37 38 39
 24 25 26 27 28 29 30 31
 16 17 18 19 20 21 22 23
  8  9 10 11 12 13 14 15
  0  1  2  3  4  5  6  7
\end{verbatim}

Many bitboard operations are simple straight-forward operations such as
bitwise-AND, but mirroring and rotating bitboards can take up to 20
instructions on x86.

\subsection{Mirroring bitboards}

Flipping horizontally or vertically can easily done with {\tt grevi}:

\begin{verbatim}
Flip horizontal:
 63 62 61 60 59 58 57 56    XBitmanip:
 55 54 53 52 51 50 49 48       brev.b
 47 46 45 44 43 42 41 40
 39 38 37 36 35 34 33 32
 31 30 29 28 27 26 25 24    x86:
 23 22 21 20 19 18 17 16       13 operations
 15 14 13 12 11 10  9  8
  7  6  5  4  3  2  1  0

Flip vertical:
  0  1  2  3  4  5  6  7    XBitmanip:
  8  9 10 11 12 13 14 15       bswap
 16 17 18 19 20 21 22 23
 24 25 26 27 28 29 30 31
 32 33 34 35 36 37 38 39    x86:
 40 41 42 43 44 45 46 47       bswap
 48 49 50 51 52 53 54 55
 56 57 58 59 60 61 62 63
\end{verbatim}

Rotating by 180 (flip horizontal and vertical):

\begin{verbatim}
Rotate 180:
  7  6  5  4  3  2  1  0    XBitmanip:
 15 14 13 12 11 10  9  8       brev
 23 22 21 20 19 18 17 16
 31 30 29 28 27 26 25 24
 39 38 37 36 35 34 33 32    x86:
 47 46 45 44 43 42 41 40       14 operations
 55 54 53 52 51 50 49 48
 63 62 61 60 59 58 57 56
\end{verbatim}

\subsection{Rotating bitboards}

Using {\tt gzip} a bitboard can be transposed easily:

\begin{verbatim}
Transpose:
  7 15 23 31 39 47 55 63    XBitmanip:
  6 14 22 30 38 46 54 62       zip, zip, zip
  5 13 21 29 37 45 53 61
  4 12 20 28 36 44 52 60
  3 11 19 27 35 43 51 59    x86:
  2 10 18 26 34 42 50 58       18 operations
  1  9 17 25 33 41 49 57
  0  8 16 24 32 40 48 56
\end{verbatim}

A rotation is simply the composition of a flip operation and a transpose
operation. This takes 19 operations on x86~\cite{ChessProg}. With XBitmanip
the rotate operation only takes 4 operations:

\begin{verbatim}
rotate_bitboard:
  bswap a0, a0
  zip a0, a0
  zip a0, a0
  zip a0, a0
\end{verbatim}

\subsection{Explanation}

The bit indices for a 64-bit word are 6 bits wide. Let $\texttt{i[5:0]}$ be the
index of a bit in the input, and let $\texttt{i$'$[5:0]}$ be the index of the
same bit after the permutation.

As an example, a rotate left shift by $N$ can be expressed using this notation
as $\texttt{i$'$[5:0]} = \texttt{i[5:0]} + N \,\,\, (\textrm{mod 64})$.

The GREV operation with shamt $N$ is $\texttt{i$'$[5:0]} = \texttt{i[5:0]} \textrm{ XOR } N$.

And a GZIP operation corresponds to a rotate left shift by one position of any
continous region of $\texttt{i[5:0]}$. For example, {\tt zip} is a left rotate shift
of the entire bit index:

$$\texttt{i$'$[5:0]} = \{ \texttt{i[4:0]},\, \texttt{i[5]} \}$$

And {\tt zip4} performs a left rotate shift on bits {\tt 5:2}:

$$\texttt{i$'$[5:0]} = \{ \texttt{i[4:2]},\, \texttt{i[5]},\, \texttt{i[1:0]} \}$$

In a bitboard, $\texttt{i[2:0]}$ corresponds to the X coordinate of a board position, and
$\texttt{i[5:3]}$ corresponds to the Y coordinate.

Therefore flipping the board horizontally is the same as negating bits $\texttt{i[2:0]}$,
which is the operation performed by {\tt grevi rd, rs, 7} ({\tt brev.b}).

Likewise flipping the board vertically is done by {\tt grevi rd, rs, 56} ({\tt bswap}).

Finally, transposing corresponds by swapping the lower and upper half of $\texttt{i[5:0]}$,
or rotate shifting $\texttt{i[5:0]}$ by 3 positions. This can easily done by rotate shifting the entire
$\texttt{i[5:0]}$ by one bit position ({\tt zip}) three times.

\subsection{Rotating Bitcubes}

Let's define a bitcube as a $4 \times 4 \times 4$ cube with $x=\texttt{i[1:0]}$,
$y=\texttt{i[3:2]}$, and $z=\texttt{i[5:4]}$. Using the same methods as described
above we can easily rotate a bitcube by 90$^\circ$ around the X-, Y-, and Z-axis:

\begin{multicols}{3}
\begin{minipage}{\linewidth}
\begin{verbatim}
rotate_x:
  hswap a0, a0
  zip4 a0, a0
  zip4 a0, a0
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
rotate_y:
  brev.n a0, a0
  zip a0, a0
  zip a0, a0
  zip4 a0, a0
  zip4 a0, a0
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
rotate_z:
  nswap.h
  zip.h a0, a0
  zip.h a0, a0
\end{verbatim}
\end{minipage}
\end{multicols}

\section{Decoding RISC-V Immediates}

The following code snippets decode and sign-extend the immedate from RISC-V
S-type, B-type, J-type, and CJ-type instructions. They are nice ``nothing up my
sleeve''-examples for real-world bit permutations.

\begin{small}
\begin{center}
\begin{tabular}{p{0in}p{0.4in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.4in}p{0.6in}p{0.4in}p{0.6in}p{0.7in}l}
& & & & & & & & & & \\
                      &
\multicolumn{1}{l}{\instbit{31}} &
\multicolumn{1}{r}{\instbit{27}} &
\instbit{26} &
\instbit{25} &
\multicolumn{1}{l}{\instbit{24}} &
\multicolumn{1}{r}{\instbit{20}} &
\instbitrange{19}{15} &
\instbitrange{14}{12} &
\instbitrange{11}{7} &
\instbitrange{6}{0} \\
\cline{2-11}

&
\multicolumn{4}{|c|}{imm[11:5]} &
\multicolumn{2}{c|}{} &
\multicolumn{1}{c|}{} &
\multicolumn{1}{c|}{} &
\multicolumn{1}{c|}{imm[4:0]} &
\multicolumn{1}{c|}{} & S-type \\
\cline{2-11}

&
\multicolumn{4}{|c|}{imm[12$\vert$10:5]} &
\multicolumn{2}{c|}{} &
\multicolumn{1}{c|}{} &
\multicolumn{1}{c|}{} &
\multicolumn{1}{c|}{imm[4:1$\vert$11]} &
\multicolumn{1}{c|}{} & B-type \\
\cline{2-11}

&
\multicolumn{8}{|c|}{imm[20$\vert$10:1$\vert$11$\vert$19:12]} &
\multicolumn{1}{c|}{} &
\multicolumn{1}{c|}{} & J-type \\
\cline{2-11}

\end{tabular}

\begin{tabular}{p{0in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}p{0.05in}l}
& & & & & & & & & & \\
                      &
\instbit{15} &
\instbit{14} &
\instbit{13} &
\multicolumn{1}{c}{\instbit{12}} &
\instbit{11} &
\instbit{10} &
\instbit{9} &
\instbit{8} &
\instbit{7} &
\instbit{6} &
\multicolumn{1}{c}{\instbit{5}} &
\instbit{4} &
\instbit{3} &
\instbit{2} &
\instbit{1} &
\instbit{0} \\
\cline{2-17}

&
\multicolumn{3}{|c|}{} &
\multicolumn{11}{c|}{imm[11$\vert$4$\vert$9:8$\vert$10$\vert$6$\vert$7$\vert$3:1$\vert$5]} &
\multicolumn{2}{c|}{} & CJ-type \\
\cline{2-17}

\end{tabular}
\end{center}
\end{small}

\begin{multicols}{2}
\begin{minipage}{\linewidth}
\begin{verbatim}
  decode_s:
    li t0, 0xfe000f80
    bext a0, a0, t0
    c.slli a0, 20
    c.srai a0, 20
    ret
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
  decode_b:
    li t0, 0xeaa800aa
    rori a0, a0, 8
    grevi a0, a0, 8
    gzip a0, a0, 14
    bext a0, a0, t0
    c.slli a0, 20
    c.srai a0, 19
    ret
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
  decode_j:
    li t0, 0x800003ff
    li t1, 0x800ff000
    bext a1, a0, t1
    c.slli a1, 23
    rori a0, a0, 21
    bext a0, a0, t0
    c.slli a0, 12
    c.or a0, a1
    c.srai a0, 11
    ret
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
  // variant 1 (with XBitmanip)
  decode_cj:
    li t0, 0x28800001
    li t1, 0x000016b8
    li t2, 0xb4e00000
    li t3, 0x4b000000
    bext a1, a0, t1
    bdep a1, a1, t2
    rori a0, a0, 11
    bext a0, a0, t0
    bdep a0, a0, t3
    c.or a0, a1
    c.srai a0, 20
    ret
\end{verbatim}
\end{minipage}

\begin{minipage}{\linewidth}
\begin{verbatim}
  // variant 2 (without XBitmanip)
  decode_cj:
    srli a5, a0, 2
    srli a4, a0, 7
    c.andi a4, 16
    slli a3, a0, 3
    c.andi a5, 14
    c.add a5, a4
    andi a3, a3, 32
    srli a4, a0, 1
    c.add a5, a3
    andi a4, a4, 64
    slli a2, a0, 1
    c.add a5, a4
    andi a2, a2, 128
    srli a3, a0, 1
    slli a4, a0, 19
    c.add a5, a2
    andi a3, a3, 768
    c.slli a0, 2
    c.add a5, a3
    andi a0, a0, 1024
    c.srai a4, 31
    c.add a5, a0
    slli a0, a4, 11
    c.add a0, a5
    ret
\end{verbatim}
\end{minipage}
\end{multicols}

Or using XBitfield:

\begin{multicols}{2}
\begin{verbatim}
  decode_s:
    bfxp a0, a1, zero, 7, 5, 20
    bfxp a0, a1, a0, 25, 7, 25
    c.srai a0, 20
    ret

  decode_b:
    bfxp a0, a1, zero, 7, 1, 30
    bfxp a0, a1, a0, 25, 6, 24
    bfxp a0, a1, a0, 8, 4, 20
    bfxp a0, a1, a0, 31, 1, 31
    c.srai a0, 19
    ret

  decode_j:
    bfxp a0, a1, zero, 21, 10, 12
    bfxp a0, a1, a0, 20, 1, 22
    bfxp a0, a1, a0, 12, 8, 23
    bfxp a0, a1, a0, 31, 1, 31
    c.srai a0, 11
    ret

  decode_cj:
    bfxp a0, a1, zero, 11, 1, 24
    bfxp a0, a1, a0, 9, 2, 28
    bfxp a0, a1, a0, 8, 1, 30
    bfxp a0, a1, a0, 7, 1, 26
    bfxp a0, a1, a0, 6, 1, 27
    bfxp a0, a1, a0, 3, 3, 21
    bfxp a0, a1, a0, 2, 1, 25
    bfxp a0, a1, a0, 12, 1, 31
    c.srai a0, 20
    ret
\end{verbatim}
\end{multicols}