# Optimizing HAWK Signature Scheme Performance on ARMv8
## 3 HAWK Optimization Through Profiling
### Optimized Implementation of Critical Operations
#### 3.2.1 Optimized Implementation of Mod _small _unsigned() Function
4:uint32_tx=0;
5:uint32_tz=mp_half(R2, p);
6:d +=len*stride;
7:foruint32_tu=len;u>0;u-do
8:d -=stride;
9:uint32_tw=*d-p;
10:w +=p&tbmask(w);
11:x =mp_montymul(x,z,p,p0i);
12:x =mp_add(x,w,p);
13:endfor
14:returnx; ```
**Algorithm 5** Uint32_t mp_half. In this paper, the'sbfx' instruction is used for more efficient calculation. The'sbfx' instruction is an instruction that extracts a specific bit field from a register, expands it and stores it in the register. In other words, the lowest bit can be extracted, expanded and stored. The example code implemented in assembly is as Table 8. As a result, by using the'sbfx' instruction, the results calculated using the ‘and’ and ‘sub’ instruction can be implemented with a single ‘sbfx’ instruction. Additionally, when branches are used, performance varies depending on whether the number is odd or even. This is not a constant-time implementation. However, if implemented using the ‘sbfx’ instruction, safety can be guaranteed because the performance is the same regardless of odd or even numbers. \begin{table}
\begin{tabular}{l l} \hline \hline
**Before (Using Branch)** & **After (Using ‘sbfx’ (Ours))** \\ \hline
1: and w3, w0, \#1 & 1: sbfx w2, w0, \#0, \#1 \\
2: chz w3, \_even & 2: and w1, w1, w2 \\
3: add w0, w0, w1 & 3: add w0, w0, w1 \\
4:\_even: & 4: lsr w0, w0, \#1 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Assembly code of uint32_t mp_half()(w0: R2, w1: p, w2: temp). number, it returns 0, and if it is a negative number, it returns 0 xfffffff. When this process is divided into positive and negative cases, the value of w is as follows. when *d is Positive, \(w=*d-p\)  
when *d is Negative, \(w=*d-p+p=*d\)  
When it is a positive number, the value obtained by subtracting the decimal p value is the result of w. In the case of a negative number, p is added again, so *d is the result. In other words, when it is a negative number, subtracting and adding p is not a necessary operation. Because the first value of w(w = *d - p) can be obtained to know whether it is a positive or negative number, it is difficult to omit the operation of subtracting p. However, in the case of addition operations, it can be omitted if it is known whether the value(w = *d - p) is positive or negative. Therefore, in this paper, we propose an efficient implementation that uses the 'csel' instruction to omit the addition operation and omits tbmask to calculate w with fewer instructions. Before optimization in Table 9, tbmask(w) is calculated using the 'asr' instruction, and then the 'and' operation is performed with the p value. If w is a positive number, the result of tbmask(w) is stored in the w3 register, and since the most significant bit is 0, 0 is stored in w3. Therefore, in line 4, an addition operation is performed with the w0 register, but since it is 0, the value of the w0 register does not change. On the other hand, if w is a negative number, w3 has the value 0 xfffffff in line 2, so w3 stores the p value from the operation result in line 3. Therefore, in line 4, the value of p is added to w0, and the value of p disappears, leaving only *d.  
In the optimized implementation, in order to omit the addition operation, the initial w value (*d - p) is compared with the value of 0 in the second line to check whether it is positive or negative, and when it is negative, through the 'csel' instruction, different values are stored in w0 depending on whether it is negative or positive. The 'csel' instruction stores either w1 or w0 in w0 depending on whether the less than (lt) condition is satisfied based on the result of the comparison with 0 in the second line. If w0 is less than 0 in line 2, the value stored in the w1 register is stored in w0. Conversely, if it is greater than 0, the w0 register value is stored in the w0 register. As a result, the *d value is stored in the w1 register, and the *d - p value is stored in w0, allowing the value to be calculated for both positive and negative numbers without needing to perform the addition instruction. This process is illustrated in Figures 3 and 4.