in Source/PLCrashAsyncCompactUnwindEncoding.c [391:485]
uint32_t plcrash_async_cfe_register_encode (const uint32_t registers[], uint32_t count) {
/* Supplied count must be within supported range */
PLCF_ASSERT(count <= PLCRASH_ASYNC_CFE_PERMUTATION_REGISTER_MAX);
/*
* Use a positional encoding to encode each integer in the list as an integer value
* that is less than the previous greatest integer in the list. We know that each
* integer (numbered 1-6) may appear only once in the list.
*
* For example:
* 6 5 4 3 2 1 ->
* 5 4 3 2 1 0
*
* 6 3 5 2 1 ->
* 5 2 3 1 0
*
* 1 2 3 4 5 6 ->
* 0 0 0 0 0 0
*/
uint32_t renumbered[PLCRASH_ASYNC_CFE_PERMUTATION_REGISTER_MAX];
for (int i = 0; i < count; ++i) {
unsigned countless = 0;
for (int j = 0; j < i; ++j)
if (registers[j] < registers[i])
countless++;
renumbered[i] = registers[i] - countless - 1;
}
uint32_t permutation = 0;
/*
* Using the renumbered list, we map each element of the list (positionally) into a range large enough to represent
* the range of any valid element, as well as be subdivided to represent the range of later elements.
*
* For example, if we use a factor of 120 for the first position (encoding multiples, decoding divides), that
* provides us with a range of 0-719. There are 6 possible values that may be encoded in 0-719 (assuming later
* division by 120), the range is broken down as:
*
* 0 - 119: 0
* 120 - 239: 1
* 240 - 359: 2
* 360 - 479: 3
* 480 - 599: 4
* 600 - 719: 5
*
* Within that range, further positions may be encoded. Assuming a value of 1 in position 0, and a factor of
* 24 for position 1, the range breakdown would be as follows:
* 120 - 143: 0
* 144 - 167: 1
* 168 - 191: 2
* 192 - 215: 3
* 216 - 239: 4
*
* Note that due to the positional renumbering performed prior to this step, we know that each subsequent position
* in the list requires fewer elements; eg, position 0 may include 0-5, position 1 0-4, and position 2 0-3. This
* allows us to allocate smaller overall ranges to represent all possible elements.
*/
/* Assert that the maximum register count matches our switch() statement. */
PLCR_ASSERT_STATIC(expected_max_register_count, PLCRASH_ASYNC_CFE_PERMUTATION_REGISTER_MAX == 6);
switch (count) {
case 1:
permutation |= renumbered[0];
break;
case 2:
permutation |= (5*renumbered[0] + renumbered[1]);
break;
case 3:
permutation |= (20*renumbered[0] + 4*renumbered[1] + renumbered[2]);
break;
case 4:
permutation |= (60*renumbered[0] + 12*renumbered[1] + 3*renumbered[2] + renumbered[3]);
break;
case 5:
permutation |= (120*renumbered[0] + 24*renumbered[1] + 6*renumbered[2] + 2*renumbered[3] + renumbered[4]);
break;
case 6:
/*
* There are 6 elements in the list, 6 possible values for each element, and values may not repeat. The
* value of the last element can be derived from the values previously seen (and due to the positional
* renumbering performed above, the value of the last element will *always* be 0.
*/
permutation |= (120*renumbered[0] + 24*renumbered[1] + 6*renumbered[2] + 2*renumbered[3] + renumbered[4]);
break;
}
PLCF_ASSERT((permutation & 0x3FF) == permutation);
return permutation;
}