Exponent decode using XOR instead of SUB?

[arichardson]

I very much like the removal of the in-memory/internal format split by moving the logic into the bounds decode rather than the load/store to keep the all-zero representation of NULL.

One question I have here is why the exponent value is subtracted from CAP_MAX_E instead of being XOR'ed. An XOR should reduce the critical path by a tiny amount compared to a subtraction or does this not matter since it's only 6/5 bits?

Is the rationale for the subtract that the in-memory format still looks like a counter rather than an opaque bit pattern? I'd argue that this shouldn't really matter since I can't imagine anyone trying to decode the values by hand instead of feeding them into a tool.

I'd propose using E = CAP_MAX_E ^ ( (XLENMAX == 32) ? { T8, TE, BE } : { TE, BE } ) instead of the current subtraction or am I missing the rationale for subtraction?

[tariqkurd-repo]

Hi Alex, yes that is certainly an option. I asked Jon Woodruff recently to remind me why we went for this scheme and his reply was:

1. I think we were happy with XORing; you all were concerned about the clarity of the spec.
2. I don't think we were thinking that the "actual exponent" was CAP_MAX_E - EXP , but that EXP was the amount we shift the T or B down from the top.

So the idea is that the exponent causes the shift to be in the reverse direction, not that it strictly needs the subtraction first and then going into the existing logic.

@andresag01 wrote the equations, is this your understanding too?

[andresag01]

Hi @arichardson, thanks for reviewing and merging the draft specification!

The motivation to remove the in-memory/internal format split was to simplify the spec and avoid confusion. Relying on XORing CAP_MAX_E with the exponent would only achieve this partially! Also, keeping the XOR is likely to increase the critical path because the bounds decoding are dependent on the output of the XOR.

We felt that removing the XOR altogether was ideal, so the proposed solution is to "invert" the sense of the exponent. That is, where the T/B were shifted left (up from LSBs to MSBs, for example here) from 0 now they are shifted right (down from MSBs to LSBs) from CAP_MAX_E. The easiest way to represent the right shift is with a subtraction in the pseudo-code of the draft spec -- note that this pseudo-code is otherwise almost identical to the pseudo-code of the CHERI v9 spec!

As @tariqkurd-repo mentioned, the subtraction is not needed in hardware implementations. The XOR was completely removed so, in addition to being simpler, the expectation is that the critical path is also trimmed with the current proposal in the draft spec.

I hope the rationale behind this design decision is helpful. What do you think @arichardson?

[jonwoodruff]

Just to add to the heap; the orientation of EXP in the draft so far is not "how much bigger you are than the most-fine-grained capability", but "how far you have descended from the almighty capability," and is just a right shift from the top rather than a left shift from the bottom. The fact that there is a subtract in the spec should just be convenience for expression; maybe there is a clearer way to express it?

[arichardson]

Thanks for explaining the rationale - I was just looking at the pseudocode so didn't think about reversing the shift. I agree that the subtraction is indeed cleaner and has the same complexity (at least for hardware).

I wonder if it makes sense to add a note about this strategy (maybe a v9 difference note that can be disabled)?

[andresag01]

@arichardson: Agreed, implementation and v9 notes here would be helpful. Also, please note that this pseudo-code is provisional and ideally this will eventually become Sail.

[tariqkurd-repo]

@arichardson are we ok to close this one?

[arichardson]

@arichardson are we ok to close this one?

This discussion definitely resolved my question but the note hasn't been added yet so I think we should keep it open as an "enhancement" (P4) bug. Or maybe we should add a new label for "low priority"