sorts.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387
  1. #define USE_TI89
  2. #define USE_TI92P
  3. #define USE_V200
  4. #define FLINE_ROM_CALLS
  5. #define USE_INTERNAL_FLINE_EMULATOR
  6. #define SAVE_SCREEN
  7. #define MIN_AMS 100
  8. #include <tigcclib.h>
  9. //! Number of main loop iterations.
  10. #define ITERATIONS (1)
  11. //! Enable this define to test a variable sorted item count (for benchmarking with non-power of two sizes).
  12. //#define SCALE
  13. //! Parametrable item type, so as to make the program more generic
  14. #define item_type uint16_t
  15. //! Number of bits used for the LFSR.
  16. #define NR_BITS (14)
  17. //! Number of items
  18. #define ITEM_COUNT (1U << NR_BITS)
  19. //#define ITEM_COUNT ((1U << NR_BITS) + (1U << (NR_BITS - 1)))
  20. //#define ITEM_COUNT ((1U << NR_BITS) + (1U << (NR_BITS - 1)) + (1U << (NR_BITS - 2)))
  21. //#define ITEM_COUNT ((1U << NR_BITS) + (1U << (NR_BITS - 1)) + (1U << (NR_BITS - 2)) + (1U << (NR_BITS - 3)) + (1U << (NR_BITS - 4)))
  22. static item_type items[ITEM_COUNT] = {0};
  23. //! Number of items that get sorted.
  24. #define SORTED_ITEM_COUNT (ITEM_COUNT)
  25. static unsigned short sorted_item_count;
  26. //#define SORTED_ITEM_COUNT ((1U << NR_BITS) - (1U << (NR_BITS - 2)))
  27. //! LFSR generator patterns for 1 -> 15-bit LFSRs.
  28. #if NR_BITS==1
  29. #define XOR_MASK (0x0001)
  30. #elif NR_BITS==2
  31. #define XOR_MASK (0x0003)
  32. #elif NR_BITS==3
  33. #define XOR_MASK (0x0006)
  34. #elif NR_BITS==4
  35. #define XOR_MASK (0x000C)
  36. #elif NR_BITS==5
  37. #define XOR_MASK (0x0014)
  38. #elif NR_BITS==6
  39. #define XOR_MASK (0x0030)
  40. #elif NR_BITS==7
  41. #define XOR_MASK (0x0060)
  42. #elif NR_BITS==8
  43. #define XOR_MASK (0x00B8)
  44. #elif NR_BITS==9
  45. #define XOR_MASK (0x0110)
  46. #elif NR_BITS==10
  47. #define XOR_MASK (0x0240)
  48. #elif NR_BITS==11
  49. #define XOR_MASK (0x0500)
  50. #elif NR_BITS==12
  51. #define XOR_MASK (0x0CA0)
  52. #elif NR_BITS==13
  53. #define XOR_MASK (0x1B00)
  54. #elif NR_BITS==14
  55. #define XOR_MASK (0x3500)
  56. #elif NR_BITS==15
  57. #define XOR_MASK (0x6000)
  58. #else
  59. #error Incorrect number of bits.
  60. #endif
  61. //! Mask for the LFSR seed.
  62. #define SEED_MASK ((1U << NR_BITS) - 1)
  63. //! AUTO_INT_5 ticks
  64. volatile unsigned long count = 0;
  65. //! AUTO_INT_5 handler
  66. DEFINE_INT_HANDLER(CountTicks)
  67. {
  68. asm volatile("addq.l #1,%0" : "=g"(count));
  69. }
  70. //! Comparison function
  71. CALLBACK short cmp (const void *p1, const void *p2) {
  72. return (*(item_type*)p1) - (*(item_type*)p2);
  73. }
  74. //! A shell sort with Shell's original gap sequence.
  75. static __ATTR_LIB_C__ void old_qsort(void *list, short num_items, short size, compare_t cmp_func)
  76. {
  77. unsigned short gap,byte_gap,i,j;
  78. char *p,*a,*b,temp;
  79. for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1) // Yes, this is not a quicksort,
  80. { // but works fast enough...
  81. byte_gap=gap*(unsigned short)size;
  82. for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
  83. for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
  84. {
  85. a=p; b=p+byte_gap;
  86. if(cmp_func(a,b)<=0) break;
  87. for(j=size;j;j--)
  88. temp=*a, *a++=*b, *b++=temp;
  89. }
  90. }
  91. }
  92. //! A shell sort using the best known sequence of gaps.
  93. __ATTR_LIB_C__ void ciura_qsort(void *list, short num_items, short size, compare_t cmp_func);
  94. /*{
  95. // Best known gap sequence for shell sort, found by Marcin Ciura, and an additional term for larger arrays.
  96. static const unsigned short step[10] = {1, 4, 10, 23, 57, 132, 301, 701, 1750, 4000};
  97. unsigned short byte_gap,i,j;
  98. short k;
  99. char *p,*a,temp;
  100. for (k = 9; k >= 0; k--) {
  101. byte_gap=step[k]*(unsigned short)size;
  102. for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size) {
  103. for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap) {
  104. a=p;
  105. if(cmp_func(a,a+byte_gap)<=0) break;
  106. for(j=size;j;j--) {
  107. temp=*a, *a=*(a+byte_gap), *(a+byte_gap)=temp; a++;
  108. }
  109. }
  110. }
  111. }
  112. }*/
  113. asm("
  114. | d3 <- p
  115. | d4 <- a+byte_gap
  116. | d5 <- k, index in table
  117. | d6 <- i
  118. | d7 <- size
  119. | a2 <- cmp_func
  120. | a3 <- byte_gap
  121. | a4 <- list
  122. | a6 <- num_items * size
  123. .text
  124. .even
  125. .globl ciura_qsort
  126. ciura_qsort:
  127. movem.l %d3-%d7/%a2-%a4/%a6,-(%sp)
  128. move.l %a0,%a4 ;# list, list
  129. move.w %d1,%d7 ;# size, size
  130. move.l %a1,%a2 ;# cmp_func, cmp_func
  131. moveq #20,%d5
  132. swap %d5
  133. move.w .Lsteplast(%pc),%d5 ;#, k
  134. cmp.w #16,%d0 ;#, num_items
  135. bhi.s 4f ;#
  136. moveq #2,%d5
  137. swap %d5
  138. addq.w #1,%d5 ;#, k
  139. 4:
  140. mulu.w %d7,%d0 ;# size, num_items
  141. move.w %d0,%a6 ;# num_items, num_items.61
  142. 6:
  143. move.w %d5,%d6 ;# k, i
  144. mulu.w %d7,%d6 ;# size, i
  145. move.l %d6,%d0 ;# i, byte_gap
  146. neg.l %d0
  147. move.l %d0,%a3
  148. bra.s 7f ;#
  149. 8:
  150. moveq #0,%d0 ;# i
  151. move.w %d6,%d0 ;# i, i
  152. move.l %a4,%d3 ;# list, p
  153. add.l %d0,%d3 ;# i, p
  154. add.l %a3,%d3 ;# D.1283, p
  155. move.l %d3,%d4 ;# p, ivtmp.60
  156. sub.l %a3,%d4 ;# D.1283, ivtmp.60
  157. bra.s 9f ;#
  158. 10:
  159. move.l %d4,-(%sp) ;# ivtmp.60,
  160. move.l %d3,-(%sp) ;# p,
  161. jsr (%a2) ;#
  162. addq.l #8,%sp ;#,
  163. tst.w %d0 ;#
  164. ble.s 11f ;#
  165. move.l %d4,%a1 ;# ivtmp.60, ivtmp.47
  166. move.w %d7,%d1 ;# size, j
  167. move.l %d3,%a0 ;# p, a
  168. subq.w #1,%d1 ;#
  169. 14:
  170. move.b (%a0),%d0 ;#* a, temp
  171. move.b (%a1),(%a0)+ ;#* ivtmp.47,
  172. move.b %d0,(%a1)+ ;# temp,
  173. dbf %d1,14b ;#, j
  174. add.l %a3,%d3 ;# D.1283, p
  175. add.l %a3,%d4 ;# ivtmp.53, ivtmp.60
  176. 9:
  177. cmp.l %d3,%a4 ;# p, list
  178. bls.s 10b ;#
  179. 11:
  180. add.w %d7,%d6 ;# size, i
  181. 7:
  182. cmp.w %a6,%d6 ;# num_items.61, i
  183. bcs.s 8b ;#
  184. swap %d5
  185. subq.w #2,%d5
  186. move.w .Lstep(%pc, %d5.w),%d0
  187. swap %d5
  188. move.w %d0,%d5
  189. bne.s 6b ;#
  190. movem.l (%sp)+,%d3-%d7/%a2-%a4/%a6
  191. rts
  192. .even
  193. .Lstep:
  194. .word 0
  195. .word 1
  196. .word 4
  197. .word 10
  198. .word 23
  199. .word 57
  200. .word 132
  201. .word 301
  202. .word 701
  203. .word 1750
  204. .Lsteplast:
  205. .word 4000
  206. ");
  207. //! A shell sort with inlined comparison function and hard-coded size.
  208. // NOTE: it would be even faster if rewritten in ASM, using the TIGCCLIB qsort() as
  209. // a starting point, but that would lose the genericity over "item_type".
  210. //
  211. // But even without the rewrite, it still fulfills the purpose of showing that
  212. // if performance is what matters, than the comparison function and the element
  213. // swap SHOULD be inlined !
  214. static __ATTR_LIB_C__ void inline_shellsort(void *list, short num_items, short ignored1, compare_t ignored2)
  215. {
  216. unsigned short gap,i;
  217. item_type *p,*a,temp;
  218. for (gap = 4096; gap > 0; gap = (gap>>1) - (gap>>4)) {
  219. for(i=gap; i<((unsigned short)num_items); i++) {
  220. for(p=(item_type*)list+i-gap; p>=(item_type*)list; p -= gap) {
  221. a=p;
  222. if(*a <= *(a+gap)) break;
  223. temp=*a, *a=*(a+gap), *(a+gap)=temp;
  224. }
  225. }
  226. }
  227. }
  228. //! Fill up the array we're going to sort, using a (NR_BITS)-bit LFSR.
  229. static void fill_items(unsigned short seed) {
  230. unsigned short seq, mask;
  231. item_type *ptr;
  232. seq = seed;
  233. mask = XOR_MASK;
  234. ptr = items;
  235. do {
  236. // ASM block is optimized version of:
  237. // if (seq & 1) seq = (seq>>1) ^ XOR_MASK;
  238. // else seq = seq>>1;
  239. //
  240. // Indeed, we can always shift, and get the rightmost bit in cc
  241. // after shifting.
  242. asm volatile("lsr.w #1,%0; bcc.s 0f; eor.w %1,%0; 0: " : "=d"(seq) : "d"(mask) : "cc");
  243. *ptr++ = (item_type)seq;
  244. }
  245. while (ptr < (items + sorted_item_count - 1));
  246. *ptr++ = 0; // Don't forget the zero.
  247. }
  248. //! Check that the arrays are filled with monotonically increasing values.
  249. static unsigned short check_items(void) {
  250. item_type seq, old_seq;
  251. item_type *ptr;
  252. seq = 0;
  253. old_seq = 0;
  254. ptr = items;
  255. while (ptr < (items + sorted_item_count)) {
  256. seq = *ptr++;
  257. if (seq < old_seq) {
  258. return seq;
  259. }
  260. old_seq = seq;
  261. }
  262. return 0xFFFF;
  263. }
  264. //! Sub-routine for launching one of the sort routines.
  265. static unsigned long run_sort(unsigned short seed, void (* __ATTR_LIB_C__ sort)(void *, short, short, compare_t)) {
  266. #if ITERATIONS == 1
  267. void *p1 = (void *)0x123456, *p2 = p1, *p3 = p1;
  268. static const item_type allones = -1;
  269. static const item_type zero = 0;
  270. static const item_type onehundredandtwentythree = 123;
  271. #endif
  272. unsigned short check;
  273. unsigned short iter;
  274. unsigned long prev_count, returnedcount;
  275. prev_count = count;
  276. while (prev_count == count);
  277. count = 0;
  278. for (iter = 0; iter < ITERATIONS; iter++) {
  279. fill_items(seed);
  280. sort (items, sorted_item_count, sizeof (items[0]), cmp);
  281. }
  282. returnedcount = count;
  283. check = check_items();
  284. if(check == 0xFFFF) {
  285. #if ITERATIONS == 1
  286. p1 = bsearch (&allones, items, sorted_item_count, sizeof (items[0]), cmp);
  287. p2 = bsearch (&zero, items, sorted_item_count, sizeof (items[0]), cmp);
  288. p3 = bsearch (&onehundredandtwentythree, items, sorted_item_count, sizeof (items[0]), cmp);
  289. printf("%lu %lp %lp %lp\n", returnedcount, p1, p2, p3);
  290. #endif
  291. }
  292. else {
  293. printf("FAILED %hu %hu %lu\n", sorted_item_count, check, (unsigned long)(items[check]));
  294. }
  295. return returnedcount;
  296. }
  297. //! It's a main...
  298. void _main(void) {
  299. short rate, start;
  300. unsigned short seed;
  301. unsigned long count_old = 0, count_new = 0, count_ciura = 0, count_inlineshell = 0;
  302. //INT_HANDLER ai1;
  303. INT_HANDLER ai5;
  304. // Save the programmable timer settings, set up our interrupt handlers and timer settings.
  305. rate = PRG_getRate();
  306. start = PRG_getStart();
  307. //ai1=GetIntVec(AUTO_INT_1);
  308. ai5=GetIntVec(AUTO_INT_5);
  309. //SetIntVec(AUTO_INT_1,DUMMY_HANDLER);
  310. SetIntVec(AUTO_INT_5,CountTicks);
  311. OSSetSR(0x0200);
  312. // If AMS 1.xx and not PedroM, use a poor seed; otherwise, use FiftyMsecTick.
  313. if (AMS_1xx && *((unsigned short *)0x32) != 0x524F) {
  314. seed = (unsigned short)(255-peekIO(0x600017));
  315. }
  316. else {
  317. seed = *((volatile unsigned long*)(_rom_call_addr(4FC))) & SEED_MASK;
  318. }
  319. sorted_item_count = SORTED_ITEM_COUNT;
  320. #ifdef SCALE
  321. for (; sorted_item_count > 3; sorted_item_count -= (sorted_item_count >> 2))
  322. #endif
  323. {
  324. #if ITERATIONS == 1
  325. printf("0x%lp %hu\n", items, sorted_item_count);
  326. #endif
  327. PRG_setRate(0);
  328. PRG_setStart(0xFF);
  329. count_old = run_sort(seed, old_qsort);
  330. if (_keytest(RR_ESC)) goto end;
  331. count_new = run_sort(seed, qsort);
  332. if (_keytest(RR_ESC)) goto end;
  333. count_ciura = run_sort(seed, ciura_qsort);
  334. if (_keytest(RR_ESC)) goto end;
  335. count_inlineshell = run_sort(seed, inline_shellsort);
  336. if (_keytest(RR_ESC)) goto end;
  337. PRG_setRate(rate);
  338. PRG_setStart(start);
  339. }
  340. #if ITERATIONS > 1
  341. printf("%lu\n%lu\n%lu\n%lu\n", count_old, count_new, count_ciura, count_inlineshell);
  342. #endif
  343. end:
  344. // Restore the programmable timer settings and the interrupt handlers.
  345. SetIntVec(AUTO_INT_5,ai5);
  346. //SetIntVec(AUTO_INT_1,ai1);
  347. asm("move.l #0x27FFF,%%d0; 0: subq.l #1,%%d0; bpl.s 0b" : : : "d0","cc");
  348. GKeyFlush();
  349. OSSetSR(0x0000);
  350. GKeyIn(NULL, 0);
  351. }