Function simplicity_hasDuplicates

src/simplicity/rsort.c:265–288

Searches for duplicates in an array of 'sha256_midstate's. * If malloc fails, returns -1. * If no duplicates are found, returns 0. * If duplicates are found, returns a positive value. * * Precondition: const sha256_midstate a[len]; * len <= DAG_LEN_MAX; */

 *               len <= DAG_LEN_MAX;
 */
int simplicity_hasDuplicates(const sha256_midstate* a, uint_fast32_t len) {
  if (len < 2) return 0;
  static_assert(sizeof(a->s) * CHAR_BIT == 256, "sha256_midstate.s has unnamed padding.");
  static_assert(DAG_LEN_MAX <= UINT32_MAX, "DAG_LEN_MAX does not fit in uint32_t.");
  static_assert(DAG_LEN_MAX <= SIZE_MAX / sizeof(const sha256_midstate*), "perm array too large.");
  simplicity_assert((size_t)len <= SIZE_MAX / sizeof(const sha256_midstate*));
  const sha256_midstate **perm = simplicity_malloc(len * sizeof(const sha256_midstate*));
  uint32_t *stack = simplicity_malloc(((CHAR_COUNT - 1)*(sizeof((*perm)->s)) + 1) * sizeof(uint32_t));
  int result = perm && stack ? 0 : -1;

  if (0 <= result) {
    for (uint_fast32_t i = 0; i < len; ++i) {
      perm[i] = a + i;
    }

    const sha256_midstate *duplicate;
    rsort_ex(perm, len, &duplicate, stack);
    result = NULL != duplicate;
  }

  simplicity_free(perm);
  simplicity_free(stack);
  return result;
}