aztec-packages icon indicating copy to clipboard operation
aztec-packages copied to clipboard

feat: optimize to_radix

Open sirasistant opened this issue 6 months ago • 1 comments

When converting ToRadix, the items are outputted with field type. Knowing that, brillig_gen codegens a loop of casts of the items to the desired type. Noir expects ToRadix to output bytes, and ToBits to output bits. So it sometimes codegens casts to u8, and other times to u1. The problem is that for a u1 cast the transpiler transpiles it to another ToRadix call, so in the case of ToBits, we are doing N extra decompositions (due to the u1 casting), where N is the number of bits. For example, for a decomposition of a Field, we'd have 255 toradix calls executed

This PR follows this approach:

  • We can change the ToRadix gadget/blackbox to emit u8 limbs instead of fields
  • We modify the toradix blackbox in brillig with an output_bits flag, to emit u1 limbs
  • No casting is needed in either case (u8 or u1) saving some emitted brillig opcodes
  • The AVM transpiler, then ignores the output_bits flag, since it'll output u8s which is what the AVM expects for bits

sirasistant avatar Aug 19 '24 16:08 sirasistant