SHARE
TWEET

Untitled

a guest Jan 25th, 2018 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. h// Programs for finding the leftmost 0-byte in a word.
  2. // Max line length is 57, to fit in hacker.book.
  3. #include <stdio.h>
  4. #include <stdlib.h>     // To define "exit", req'd by XLC.
  5.  
  6. int nlz(unsigned x) {
  7.    int n;
  8.  
  9.    if (x == 0) return(32);
  10.    n = 0;
  11.    if (x <= 0x0000FFFF) {n = n +16; x = x <<16;}
  12.    if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;}
  13.    if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;}
  14.    if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;}
  15.    if (x <= 0x7FFFFFFF) {n = n + 1;}
  16.    return n;
  17. }
  18.  
  19. // Find leftmost 0-byte, simple sequence of tests.
  20. int zbytel1(unsigned x) {
  21.    if             ((x >> 24) == 0) return 0;
  22.    else if ((x & 0x00FF0000) == 0) return 1;
  23.    else if ((x & 0x0000FF00) == 0) return 2;
  24.    else if ((x & 0x000000FF) == 0) return 3;
  25.    else return 4;
  26. }
  27.  
  28. // Find leftmost 0-byte, branch-free code.
  29. int zbytel2(unsigned x) {
  30.    unsigned y;
  31.    int n;
  32.                          // Original byte: 00 80 other
  33.    y = (x & 0x7F7F7F7F) + 0x7F7F7F7F;   // 7F 7F 1xxxxxxx
  34.    y = ~(y <PIPE> x <PIPE> 0x7F7F7F7F);           // 80 00 00000000
  35.    n = nlz(y) >> 3;             // n = 0 ... 4, 4 if x
  36.    return n;                    // has no 0-byte.
  37. }
  38.  
  39. // Find leftmost 0-byte, not using nlz.
  40. int zbytel3(unsigned x) {
  41.    unsigned y;
  42.                        // Original byte: 00 80 other
  43.    y = (x & 0x7F7F7F7F) + 0x7F7F7F7F; // 7F 7F 1xxxxxxx
  44.    y = ~(y <PIPE> x <PIPE> 0x7F7F7F7F);         // 80 00 00000000
  45.                                       // These steps map:
  46.    if (y == 0) return 4;              // 00000000 ==> 4,
  47.    else if (y > 0x0000FFFF)           // 80xxxxxx ==> 0,
  48.       return (y >> 31) ^ 1;           // 0080xxxx ==> 1,
  49.    else                               // 000080xx ==> 2,
  50.       return (y >> 15) ^ 3;           // 00000080 ==> 3.
  51. }
  52.  
  53. int zbytel3a(unsigned x) {
  54.    unsigned y;
  55.    static char table[16] = {4, 3, 2, 2, 1, 1, 1, 1,
  56.                             0, 0, 0, 0, 0, 0, 0, 0};
  57.                        // Original byte: 00 80 other
  58.    y = (x & 0x7F7F7F7F) + 0x7F7F7F7F; // 7F 7F 1xxxxxxx
  59.    y = ~(y <PIPE> x <PIPE> 0x7F7F7F7F);         // 80 00 00000000
  60.    return table[y*0x00204081 >> 28];
  61. }
  62.  
  63. // Find leftmost 0-byte by evaluating a polynomial.
  64. int zbytel4(unsigned x) {
  65.    unsigned y, t1, t2, t3, t4;
  66.  
  67.    y = (x & 0x7F7F7F7F) + 0x7F7F7F7F;
  68.    y = y <PIPE> x;           // Leading 1 on nonzero bytes.
  69.  
  70.    t1 =  y >> 31;               // t1 = a.
  71.    t2 = (y >> 23) & t1;         // t2 = ab.
  72.    t3 = (y >> 15) & t2;         // t3 = abc.
  73.    t4 = (y >>  7) & t3;         // t4 = abcd.
  74.    return t1 + t2 + t3 + t4;
  75. }
  76.  
  77. // Find leftmost byte having value le 9.
  78. int valle9(unsigned x) {
  79.    unsigned y;
  80.    int n;
  81.  
  82.    y = (x & 0x7F7F7F7F) + 0x76767676;
  83.    y = y <PIPE> x;
  84.    y = y <PIPE> 0x7F7F7F7F;          // Bytes > 9 are 0xFF.
  85.    y = ~y;                      // Bytes > 9 are 0x00,
  86.                                 // bytes <= 9 are 0x80.
  87.    n = nlz(y) >> 3;
  88.    return n;
  89. }
  90.  
  91. // Find leftmost byte having an upper case letter.
  92. int valupcase(unsigned x) {
  93.    unsigned d, y;
  94.    int n;
  95.  
  96.    d = (x <PIPE> 0x80808080) - 0x41414141;
  97.    d = ~((x <PIPE> 0x7F7F7F7F) ^ d);
  98.    y = (d & 0x7F7F7F7F) + 0x66666666;
  99.    y = y <PIPE> d;
  100.    y = y <PIPE> 0x7F7F7F7F;    // Bytes not from 41-5A are FF.
  101.    y = ~y;                // Bytes not from 41-5A are 00,
  102.                           // bytes from 41-5A are 80.
  103.    n = nlz(y) >> 3;
  104.    return n;
  105. }
  106.  
  107. int errors;
  108. void error(int x, int y) {
  109.    errors = errors + 1;
  110.    printf("Error for x = %08x, got %d\n", x, y);
  111. }
  112.  
  113. int main() {
  114.    int i, r, n;
  115.    static unsigned test[] = {0x00000000,0, 0x00000001,0,
  116.       0x00800000,0, 0x00FFFFFF,0,
  117.       0x01000000,1, 0x0100FFFF,1, 0x7F000000,1, 0x8000FFFF,1,
  118.       0x01010000,2, 0x010100FF,2, 0x7F7F0000,2, 0xFFFF00FF,2,
  119.       0x01010100,3, 0x01017F00,3, 0x7F7F8000,3, 0xFFFFFF00,3,
  120.       0x01010101,4, 0x80808080,4, 0x7F7F7F7F,4, 0xFFFFFFFF,4};
  121.  
  122.    static unsigned test2[] = {0x00000000,0, 0x00000001,0,
  123.       0x09000000,0, 0x09FFFFFF,0, 0x0A010000,1, 0x1909FFFF,1,
  124.       0xFF0A0000,2, 0x80800900,2, 0x81810980,2, 0xFEFE0822,2,
  125.       0x0A0A0A00,3, 0x0A0A0A09,3, 0x0A0A0A07,3, 0xFFFFFF01,3,
  126.       0x0A0A0A0A,4, 0xFFFFFFFF,4, 0x80808080,4, 0x7F7F7F7F,4};
  127.  
  128.    static unsigned test3[] = {0x00000000,4, 0x00000001,4,
  129.       0x40000000,4, 0x40FFFFFF,4, 0x41000000,0, 0x41FFFFFF,0,
  130.       0x5A000000,0, 0x5AFFFFFF,0, 0x5B000000,4, 0x5BFFFFFF,4,
  131.       0x00400000,4, 0xFF40FFFF,4, 0x00410000,1, 0xFF41FFFF,1,
  132.       0x005A0000,1, 0xFF5AFFFF,1, 0x005B0000,4, 0xFF5BFFFF,4,
  133.       0x80804080,4, 0x80804180,2, 0x80805A80,2, 0x80805B80,4,
  134.       0x7F7F7F40,4, 0x7F7F7F41,3, 0x7F7F7F5A,3, 0x7F7F7F5B,4,
  135.       0x41414141,0, 0x5A5A5A5A,0, 0x40404141,2, 0x5B5B5A5A,2,
  136.       0x80808080,4, 0x7F7F7F7F,4, 0xFFFFFFFF,4};
  137.  
  138.    n = sizeof(test)/4;
  139.  
  140.    printf("zbytel1:\n");
  141.    for (i = 0; i < n; i += 2) {
  142.       r = zbytel1(test[i]);
  143.       if (r != test[i+1]) error(test[i], r);}
  144.  
  145.    printf("zbytel2:\n");
  146.    for (i = 0; i < n; i += 2) {
  147.       r = zbytel2(test[i]);
  148.       if (r != test[i+1]) error(test[i], r);}
  149.  
  150.    printf("zbytel3:\n");
  151.    for (i = 0; i < n; i += 2) {
  152.       r = zbytel3(test[i]);
  153.       if (r != test[i+1]) error(test[i], r);}
  154.  
  155.    printf("zbytel3a:\n");
  156.    for (i = 0; i < n; i += 2) {
  157.       r = zbytel3a(test[i]);
  158.       if (r != test[i+1]) error(test[i], r);}
  159.  
  160.    printf("zbytel4:\n");
  161.    for (i = 0; i < n; i += 2) {
  162.       r = zbytel4(test[i]);
  163.       if (r != test[i+1]) error(test[i], r);}
  164.  
  165.    if (errors == 0)
  166.       printf("Passed all %d cases.\n", n/2);
  167.  
  168.    n = sizeof(test2)/4;
  169.  
  170.    printf("valle9:\n");
  171.    for (i = 0; i < n; i += 2) {
  172.       r = valle9(test2[i]);
  173.       if (r != test2[i+1]) error(test2[i], r);}
  174.  
  175.    if (errors == 0)
  176.       printf("Passed all %d cases.\n", n/2);
  177.  
  178.    n = sizeof(test3)/4;
  179.  
  180.    printf("valupcase:\n");
  181.    for (i = 0; i < n; i += 2) {
  182.       r = valupcase(test3[i]);
  183.       if (r != test3[i+1]) error(test3[i], r);}
  184.  
  185.    if (errors == 0)
  186.       printf("Passed all %d cases.\n", n/2);
  187. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top