102 Dalmatians: Puppies to the Rescue
Decompilation Source Reference | GitLab repository
Loading...
Searching...
No Matches
sorting.c
Go to the documentation of this file.
1/* Recovered game implementation; original addresses identify provenance. */
4#include <intrin.h>
5#include <math.h>
6#include <stdarg.h>
7#include <string.h>
8
9// Original pcdogs.exe: 0x446406
10// Sorts fixed-size elements with an iterative quicksort and a small-range selection-sort fallback. Empty ranges and zero-sized elements require no work.
11void CRT_qsort(void *base, uint32_t count, uint32_t element_size, int32_t (*compare)(void const *, void const *))
12{
13 if (count < 2 || !element_size)
14 return;
15
16 int32_t pending_partition_count = 0;
17 char *first_element = base;
18 char *partition_high_stack[30];
19 char *last_element = (count - 1) * element_size + first_element;
20 char *partition_low_stack[30];
21
22 while (true)
23 {
24 uint64_t partition_count = (uint64_t)(uint32_t)(last_element - first_element) / element_size + 1;
25
26 if (partition_count > 8)
27 {
29 (partition_count >> 1) * element_size + first_element,
30 first_element, element_size);
31
32 char *left_scan = first_element;
33 char *right_scan = &last_element[element_size];
34
35 while (true)
36 {
37 left_scan += element_size;
38
39 if (left_scan <= last_element && compare(left_scan, first_element) <= 0)
40 continue;
41
42 bool right_at_least_pivot;
43
44 do
45 {
46 right_scan -= element_size;
47
48 if (right_scan <= first_element)
49 break;
50
51 right_at_least_pivot = compare(right_scan, first_element) >= 0;
52 } while (right_at_least_pivot);
53
54 if (right_scan < left_scan)
55 break;
56
57 CRT_swap(left_scan, right_scan, element_size);
58 }
59
60 CRT_swap(first_element, right_scan, element_size);
61
62 if (right_scan - first_element - 1 < last_element - left_scan)
63 {
64 if (left_scan < last_element)
65 {
66 partition_low_stack[pending_partition_count] = left_scan;
67 partition_high_stack[pending_partition_count] = last_element;
68 ++pending_partition_count;
69 }
70
71 if (&first_element[element_size] < right_scan)
72 {
73 last_element = right_scan - element_size;
74
75 continue;
76 }
77 }
78 else
79 {
80 if (&first_element[element_size] < right_scan)
81 {
82 partition_low_stack[pending_partition_count] = first_element;
83 partition_high_stack[pending_partition_count] = right_scan - element_size;
84 ++pending_partition_count;
85 }
86
87 if (left_scan < last_element)
88 {
89 first_element = left_scan;
90
91 continue;
92 }
93 }
94 }
95 else
96 CRT_shortsort(first_element, last_element, element_size, compare);
97
98 if (!pending_partition_count)
99 break;
100
101 --pending_partition_count;
102 first_element = partition_low_stack[pending_partition_count];
103 last_element = partition_high_stack[pending_partition_count];
104 }
105}
106
107// Original pcdogs.exe: 0x44655a
108// Sorts an inclusive small range by repeatedly selecting its greatest element and moving it to the shrinking end.
109void CRT_shortsort(char *first_element, char *last_element, uint32_t element_size, int32_t (*compare)(void const *, void const *))
110{
111 for (char *unsorted_end = last_element; unsorted_end > first_element; unsorted_end -= element_size)
112 {
113 char *maximum_element = first_element;
114
115 for (char *candidate = &first_element[element_size]; candidate <= unsorted_end; candidate = &candidate[element_size])
116 {
117 if (compare(candidate, maximum_element) > 0)
118 maximum_element = candidate;
119 }
120
121 CRT_swap(maximum_element, unsorted_end, element_size);
122 }
123}
124
125// Original pcdogs.exe: 0x4465a8
126// Swaps two elements byte by byte, doing nothing when their addresses match or their size is zero.
127void CRT_swap(char *dest, char *src, uint32_t count)
128{
129 if (dest == src || !count)
130 return;
131
132 do
133 {
134 char saved_byte = *(uint8_t *)dest;
135
136 *(uint8_t *)dest = *(uint8_t *)src;
137 dest = &dest[1];
138 *(uint8_t *)src = saved_byte;
139 src = &src[1];
140 } while (--count);
141}
void CRT_qsort(void *base, uint32_t count, uint32_t element_size, int32_t(*compare)(void const *, void const *))
Definition sorting.c:11
void CRT_shortsort(char *first_element, char *last_element, uint32_t element_size, int32_t(*compare)(void const *, void const *))
Definition sorting.c:109
void CRT_swap(char *dest, char *src, uint32_t count)
Definition sorting.c:127