1c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 2c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil#include <linux/types.h> 33d14c5d2b6e15c21d8e5467dc62d33127c23a644Yehuda Sadeh#include <linux/crush/hash.h> 4c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 5c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil/* 6c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil * Robert Jenkins' function for mixing 32-bit values 7c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil * http://burtleburtle.net/bob/hash/evahash.html 8c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil * a, b = random bits, c = input and output 9c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil */ 10c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil#define crush_hashmix(a, b, c) do { \ 11c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil a = a-b; a = a-c; a = a^(c>>13); \ 12c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil b = b-c; b = b-a; b = b^(a<<8); \ 13c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil c = c-a; c = c-b; c = c^(b>>13); \ 14c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil a = a-b; a = a-c; a = a^(c>>12); \ 15c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil b = b-c; b = b-a; b = b^(a<<16); \ 16c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil c = c-a; c = c-b; c = c^(b>>5); \ 17c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil a = a-b; a = a-c; a = a^(c>>3); \ 18c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil b = b-c; b = b-a; b = b^(a<<10); \ 19c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil c = c-a; c = c-b; c = c^(b>>15); \ 20c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil } while (0) 21c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 22c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil#define crush_hash_seed 1315423911 23c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 24fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilstatic __u32 crush_hash32_rjenkins1(__u32 a) 25c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil{ 26c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 hash = crush_hash_seed ^ a; 27c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 b = a; 28c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 x = 231232; 29c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 y = 1232; 30c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(b, x, hash); 31c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, a, hash); 32c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil return hash; 33c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil} 34c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 35fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilstatic __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b) 36c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil{ 37c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 hash = crush_hash_seed ^ a ^ b; 38c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 x = 231232; 39c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 y = 1232; 40c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(a, b, hash); 41c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(x, a, hash); 42c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(b, y, hash); 43c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil return hash; 44c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil} 45c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 46fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilstatic __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c) 47c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil{ 48c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 hash = crush_hash_seed ^ a ^ b ^ c; 49c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 x = 231232; 50c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 y = 1232; 51c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(a, b, hash); 52c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(c, x, hash); 53c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, a, hash); 54c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(b, x, hash); 55c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, c, hash); 56c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil return hash; 57c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil} 58c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 59fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilstatic __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d) 60c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil{ 61c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d; 62c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 x = 231232; 63c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 y = 1232; 64c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(a, b, hash); 65c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(c, d, hash); 66c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(a, x, hash); 67c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, b, hash); 68c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(c, x, hash); 69c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, d, hash); 70c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil return hash; 71c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil} 72c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil 73fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilstatic __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d, 74fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil __u32 e) 75c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil{ 76c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e; 77c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 x = 231232; 78c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil __u32 y = 1232; 79c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(a, b, hash); 80c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(c, d, hash); 81c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(e, x, hash); 82c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, a, hash); 83c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(b, x, hash); 84c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, c, hash); 85c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(d, x, hash); 86c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil crush_hashmix(y, e, hash); 87c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil return hash; 88c6cf726316abd613cfb7c325d950f3629f964ec6Sage Weil} 89fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 90fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 91fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil__u32 crush_hash32(int type, __u32 a) 92fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 93fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 94fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 95fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return crush_hash32_rjenkins1(a); 96fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 97fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return 0; 98fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 99fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 100fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 101fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil__u32 crush_hash32_2(int type, __u32 a, __u32 b) 102fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 103fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 104fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 105fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return crush_hash32_rjenkins1_2(a, b); 106fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 107fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return 0; 108fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 109fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 110fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 111fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil__u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c) 112fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 113fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 114fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 115fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return crush_hash32_rjenkins1_3(a, b, c); 116fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 117fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return 0; 118fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 119fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 120fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 121fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil__u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d) 122fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 123fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 124fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 125fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return crush_hash32_rjenkins1_4(a, b, c, d); 126fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 127fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return 0; 128fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 129fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 130fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 131fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil__u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e) 132fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 133fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 134fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 135fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return crush_hash32_rjenkins1_5(a, b, c, d, e); 136fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 137fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return 0; 138fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 139fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 140fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil 141fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weilconst char *crush_hash_name(int type) 142fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil{ 143fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil switch (type) { 144fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil case CRUSH_HASH_RJENKINS1: 145fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return "rjenkins1"; 146fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil default: 147fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil return "unknown"; 148fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil } 149fb690390e305ea51e1883b105c7d3c52d7100ba5Sage Weil} 150