common/bucketsort.c

   1 //-----------------------------------------------------------------------------
   2 // Copyright (C) Proxmark3 contributors. See AUTHORS.md for details.
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU General Public License as published by
   6 // the Free Software Foundation, either version 3 of the License, or
   7 // (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13 //
  14 // See LICENSE.txt for the text of the license.
  15 //-----------------------------------------------------------------------------
  16 #include "bucketsort.h"
  17
  18 extern void bucket_sort_intersect(uint32_t *const estart, uint32_t *const estop,
  19                                   uint32_t *const ostart, uint32_t *const ostop,
  20                                   bucket_info_t *bucket_info, bucket_array_t bucket) {
  21     uint32_t *p1, *p2;
  22     uint32_t *start[2];
  23     uint32_t *stop[2];
  24
  25     start[0] = estart;
  26     stop[0] = estop;
  27     start[1] = ostart;
  28     stop[1] = ostop;
  29
  30     // init buckets to be empty
  31     for (uint32_t i = 0; i < 2; i++) {
  32         for (uint32_t j = 0x00; j <= 0xff; j++) {
  33             bucket[i][j].bp = bucket[i][j].head;
  34         }
  35     }
  36
  37     // sort the lists into the buckets based on the MSB (contribution bits)
  38     for (uint32_t i = 0; i < 2; i++) {
  39         for (p1 = start[i]; p1 <= stop[i]; p1++) {
  40             uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
  41             *(bucket[i][bucket_index].bp++) = *p1;
  42         }
  43     }
  44
  45     // write back intersecting buckets as sorted list.
  46     // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
  47     for (uint32_t i = 0; i < 2; i++) {
  48         p1 = start[i];
  49         uint32_t nonempty_bucket = 0;
  50         for (uint32_t j = 0x00; j <= 0xff; j++) {
  51             if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
  52                 bucket_info->bucket_info[i][nonempty_bucket].head = p1;
  53                 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
  54                 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
  55                 nonempty_bucket++;
  56             }
  57         }
  58         bucket_info->numbuckets = nonempty_bucket;
  59     }
  60 }