fork download
copy 
  1. /* Find fixpoints and cycles in base64 -- Antoine Amarilli, 2013
  2.  * Usage: ./a.out for standard base64 
  3.  *        ./a.out TABLE for custom encoding (must have strlen(table) == 64) */ 
  4.  
  5. #include <stdio.h>
  6. #include <assert.h>
  7. #include <string.h>
  8.  
  9. // The base64 table
  10. char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  11.  
  12. /* Will contain:
  13.  * -1 if uninitialized
  14.  * <-1 if being currently explored
  15.  * >0 is distance to a stable configuration (a fixpoint or a cycle member) */
  16. int graph[256][256][256];
  17.  
  18. int explore(unsigned char i, unsigned char j, unsigned char k, int d) {
  19.   /* encode ijk until reaching a fixpoint or cycle,
  20.    * return distance to a stable configuration
  21.    * (or <0 if within stable configuration),
  22.    * d is the current distance travelled */
  23.  
  24.   if (graph[i][j][k] >= 0) {
  25.     // we know how to reach fixpoint from here in that many hops
  26.     return graph[i][j][k];
  27.   }
  28.   if (graph[i][j][k] < -1) {
  29.     // we hit something in the current stack
  30.     // retrieve the cycle length from the current d and store value
  31.     int period = d + graph[i][j][k] + 1;
  32.     printf("Stable configuration of period %d: %c%c%c alias %d %d %d\n",
  33.         period, i, j, k, i, j, k);
  34.     // unwind the stack: return the negative length of the cycle so that all
  35.     // cycle members are set to zero
  36.     return -period-1;
  37.   }
  38.   // mark that we are exploring this node and the distance traveled
  39.   graph[i][j][k] = -2 - d;
  40.   unsigned char u,v,w;
  41.   u = (i&~0x03)>>2;
  42.   v = (i&0x03)<<4 | (j&~0x0F)>>4;
  43.   w = (j&0x0F)<<2 | (k&~0x3F)>>6;
  44.   int ret = explore(b64[u], b64[v], b64[w], d+1);
  45.   if (ret >= 0) {
  46.     // our distance to stable is one plus distance to stable of our image
  47.     graph[i][j][k] = ret+1;
  48.   } else {
  49.     // we are unwinding a stable configuration
  50.     graph[i][j][k] = 0;
  51.   }
  52.   // return our distance to stable, or continue unwinding
  53.   return ret+1;
  54. }
  55.  
  56. int main(int argc, char **argv) {
  57.   int i, j, k;
  58.   // initialization
  59.   for (i=0; i<256; i++)
  60.     for (j=0; j<256; j++)
  61.       for (k=0; k<256; k++)
  62.         graph[i][j][k] = -1;
  63.   if (argc == 2) {
  64.     // a custom table has been passed
  65.     assert(strlen(argv[1]) == 64);
  66.     b64 = argv[1];
  67.   }
  68.   int max = 0;
  69.   int ret;
  70.   unsigned char va=0, vb=0, vc=0;
  71.   for (i=0; i<256; i++)
  72.     for (j=0; j<256; j++)
  73.       for (k=0; k<256; k++) {
  74.         ret = explore(i, j, k, 0);
  75.         if (ret > max) {
  76.           max = ret;
  77.           va = i; vb = j; vc = k;
  78.         }
  79.       }
  80.  
  81.   // print which is the longest way to reach a stable configuration
  82.   printf("Longest chain is from %d %d %d (%d hops)\n", va, vb, vc, max);
  83.   return 0;
  84. }
  85.  
  86.  
Success #stdin #stdout 0.42s 67392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Stable configuration of period 0: Vm0 alias 86 109 48
Longest chain is from 132 0 0 (9 hops)
https://ideone.com/6byO8N
language:
C (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!