# Lightweight Conversion from Arithmetic to Boolean Masking for Embedded IoT Processor
## 2 Background
### The A2B Algorithm Based on the Ripple-Carry Adder
#### 2.3.2 [PERSON]'s A2B Algorithm
Proof: It can be easily proven by the definition of Table \(C\)

\[C[\gamma]=\alpha\cdot 2^{k},\;C[\gamma\oplus 1]=(\alpha+1)\cdot 2^{k}\]

That is, the result of \(C[t]\) is \(\alpha\cdot 2^{k}\) when c is 0 and \((\alpha+1)\cdot 2^{k}\) when c is 1. When table \(C\) is added to \(A\), we designed \(\alpha\) of the next converted block to be naturally removed by \(-\Gamma(=-\sum_{l=1}^{n-1}(\alpha\cdot 2^{l\cdot k}))\) at Line 1. Consequently, the correct carry bit is added, and thus Line 6 is valid. The end of the initial for loop is as follows. \[\text{(Line 7)} \tag{7}\] \[(\dot{x}_{k}^{n-1}||0_{0}^{k-1})-(R_{k}^{n-1}||0_{0}^{k-1})-(r||...|| r||0_{0}^{k-1})-\sum_{l=2}^{n-1}(\alpha\cdot 2^{l\cdot k})\]

\(\dot{x}\) is a sensitive value computed for the carry bit. _Inductive hypothesis:_ Suppose the algorithm holds for \(i=a\) before the **for** loop. Then, \(A=(x_{a\cdot k}^{n-1}||0_{0}^{a\cdot k-1})-(R_{a\cdot k}^{n-1}||0_{0}^{a\cdot k -1})-(r||...||r||0_{0}^{a\cdot k-1})-\sum_{l=a+1}^{n-1}(\alpha\cdot 2^{l\cdot k})\). Additionally, suppose the algorithm holds for \(i=a+1\) before the for loop. Then, \(A=(x_{a+1\cdot k}^{n-1}||0_{0}^{(a+1)\cdot k-1})-(R_{(a+1)\cdot k}^{n-1}||0_{ 0}^{(a+1)\cdot k-1})-(r||...||r||0_{0}^{(a+1)\cdot k-1})-\sum_{l=a+2}^{n-1}( \alpha\cdot 2^{l\cdot k})\). _Inductive step:_ Show that if \(i=a\) of the **for** loop holds, then \(i=a+1\) of the **for** loop also holds. We proved this step, as shown in Table 5. This table shows that \(i=a+1\) at the end of the **for** loop indeed holds. Thus, the inductive case holds. Now, by mathematical induction, our A2B algorithm works correctly for an arbitrary \(k,n\) Q.E.D. ## 5 Performance Analysis

We summarize the performance of the proposed algorithm, [PERSON]'s algorithm ([22]), and [PERSON]'s algorithm ([17]) in Table 6. The proposed algorithms have advantages in terms of the memory usage and the execution time of the pre-computation phase like [17]. The execution time of the A2B conversion phase with the LSB trick also shows good performance in various environments. To summarize, one of the advantages in terms of memory usage is that it uses approximatively half the memory in the pre-computation phase compared to [PERSON]'s algorithm. Another advantage in terms of memory usage is that the data type of our pre-computation table is compact and reasonable in real devices, because typical devices only support char, short, and int. The advantage in the execution time of the pre-computation phase is that it requires approximately half the time that [PERSON]'s does, as the table only has half as many entries. In the conversion phase, the operations of the ADD/SUB, XOR/AND and SHIFT are very similar in the three algorithms; however, the proposed algorithm has slightly fewer operators. To count the operations, we counted the number of operators with the following rules. - In Algorithm 5, the concatenating process at Line 6 (front) as one AND. - In Algorithm 5, the concatenating process at Line 6 (rear) as one SHIFT, one AND, and one XOR. - In Algorithm 6, the concatenating process at Line 3 and 4 (front) as one SHIFT and one XOR. - In Algorithm 6, the concatenating process at Line 3 and 4 (rear) as one SHIFT and one XOR. (Computes only once)

- In Algorithm 7, the splitting process at Line 4 as two SHIFTs and two ANDs. - In Algorithm 7, the modulus at the Line 5 as one AND. - In Algorithm 7, the concatenating at the Line 6 (front) as one SHIFT and one AND. - In Algorithm 7, the concatenating at the Line 6 (rear) as one SHIFT, one AND, and one XOR. - In Algorithm 8, the concatenating process at Line 3 as one SHIFT and one XOR. (Computes only once)

- In Algorithm 9, the concatenating process at Line 4 (front) as one SHIFT and one AND. - In Algorithm 9, the concatenating process at Line 4 (rear) as one SHIFT, one AND, and one XOR.