vfs/util.d

   1 /* Invisible Vector Library
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, version 3 of the License ONLY.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 // VFS utils
  18 module iv.vfs.util /*is aliced*/;
  19 import iv.alice;
  20
  21
  22 public void arrayAppendUnsafe(T) (ref T[] arr, auto ref T val) {
  23   auto xptr = arr.ptr;
  24   arr ~= val;
  25   if (arr.ptr !is xptr) {
  26     import core.memory : GC;
  27     xptr = arr.ptr;
  28     if (xptr is GC.addrOf(xptr)) GC.setAttr(xptr, GC.BlkAttr.NO_INTERIOR);
  29   }
  30 }
  31
  32 public void arraySetLengthUnsafe(T) (ref T[] arr, usize len) {
  33   if (len < arr.length) {
  34     arr.length = len;
  35     arr.assumeSafeAppend;
  36   } else {
  37     auto xptr = arr.ptr;
  38     arr.length = len;
  39     if (arr.ptr !is xptr) {
  40       import core.memory : GC;
  41       xptr = arr.ptr;
  42       if (xptr is GC.addrOf(xptr)) GC.setAttr(xptr, GC.BlkAttr.NO_INTERIOR);
  43     }
  44   }
  45 }
  46
  47
  48 public uint crc32 (const(void)[] buf, uint crc=0) pure nothrow @trusted @nogc {
  49   /*
  50   static immutable uint[16] crctab = [
  51     0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
  52     0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
  53     0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
  54     0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c,
  55   ];
  56   */
  57   static immutable uint[16] crctab = {
  58     uint[16] res = void;
  59     // make exclusive-or pattern from polynomial (0xedb88320u)
  60     // terms of polynomial defining this crc (except x^32)
  61     //uint poly = 0; // polynomial exclusive-or pattern
  62     //foreach (immutable n; [0,1,2,4,5,7,8,10,11,12,16,22,23,26]) poly |= 1u<<(31-n);
  63     enum poly = 0xedb88320u;
  64     foreach (immutable n; 0..16) {
  65       uint c = cast(uint)n*16;
  66       foreach (immutable k; 0..8) c = (c&1 ? poly^(c>>1) : c>>1);
  67       res[n] = c;
  68     }
  69     return res;
  70   }();
  71
  72   if (buf.length) {
  73     crc ^= 0xffff_ffffu;
  74     foreach (ubyte b; cast(const(ubyte)[])buf) {
  75       crc ^= b;
  76       crc = crctab.ptr[crc&0x0f]^(crc>>4);
  77       crc = crctab.ptr[crc&0x0f]^(crc>>4);
  78     }
  79     crc ^= 0xffff_ffffu;
  80   }
  81   return crc;
  82 }
  83
  84
  85 public uint mur3HashOf(T) (const(T)[] data, usize seed=0) pure nothrow @trusted @nogc if (T.sizeof == 1) {
  86   enum C1 = 0xcc9e2d51u;
  87   enum C2 = 0x1b873593u;
  88
  89   uint hash = seed; // current value
  90   uint accum; // we operate 32-bit chunks; low 2 bits of accum used as counter
  91   ubyte n;
  92   uint k1;
  93
  94   // process data blocks
  95   if (data.length) {
  96     auto bytes = cast(const(ubyte)*)data.ptr;
  97     auto len = data.length;
  98     // process 32-bit chunks
  99     foreach (immutable _; 0..len/4) {
 100       version(LittleEndian) {
 101         if (__ctfe) {
 102           k1 = (bytes[0])|(bytes[1]<<8)|(bytes[2]<<16)|(bytes[3]<<24);
 103         } else {
 104           k1 = *cast(const(uint)*)bytes;
 105         }
 106       } else {
 107         if (__ctfe) {
 108           k1 = (bytes[3])|(bytes[2]<<8)|(bytes[1]<<16)|(bytes[0]<<24);
 109         } else {
 110           import core.bitop : bswap;
 111           k1 = bswap(*cast(const(uint)*)bytes);
 112         }
 113       }
 114       bytes += 4;
 115       k1 *= C1;
 116       k1 = (k1<<15)|(k1>>(32-15));
 117       k1 *= C2;
 118       hash ^= k1;
 119       hash = (hash<<13)|(hash>>(32-13));
 120       hash = hash*5+0xe6546b64;
 121     }
 122     // advance over whole 32-bit chunks, possibly leaving 1..3 bytes
 123     len &= 0x03;
 124     n = cast(ubyte)len;
 125     // append any remaining bytes into carry
 126     while (len--) accum = (accum>>8)|(*bytes++<<24);
 127   }
 128
 129   // finalize a hash
 130   if (n) {
 131     k1 = accum>>(4-n)*8;
 132     k1 *= C1;
 133     k1 = (k1<<15)|(k1>>(32-15));
 134     k1 *= C2;
 135     hash ^= k1;
 136   }
 137   hash ^= cast(uint)data.length;
 138   // fmix
 139   hash ^= hash>>16;
 140   hash *= 0x85ebca6bu;
 141   hash ^= hash>>13;
 142   hash *= 0xc2b2ae35u;
 143   hash ^= hash>>16;
 144   return hash;
 145 }
 146
 147
 148 public uint mur3HashOf(R) (auto ref R rng, uint seed=0) pure nothrow @trusted @nogc
 149 if (is(typeof((inout int=0){
 150   bool e = rng.empty;
 151   ubyte b = rng.front;
 152   rng.popFront();
 153 })))
 154 {
 155   enum C1 = 0xcc9e2d51u;
 156   enum C2 = 0x1b873593u;
 157
 158   uint hash = seed; // current value
 159   ubyte n;
 160   uint k1;
 161   uint len;
 162
 163   // process data blocks
 164   // advance over whole 32-bit chunks, possibly leaving 1..3 bytes
 165   while (!rng.empty) {
 166     ++len;
 167     ubyte b = rng.front;
 168     rng.popFront();
 169     k1 |= (cast(uint)b)<<(n*8);
 170     n = (n+1)&0x03;
 171     if (n == 0) {
 172       // we have a chunk
 173       k1 *= C1;
 174       k1 = (k1<<15)|(k1>>(32-15));
 175       k1 *= C2;
 176       hash ^= k1;
 177       hash = (hash<<13)|(hash>>(32-13));
 178       hash = hash*5+0xe6546b64;
 179       k1 = 0; // reset accumulator
 180     }
 181   }
 182
 183   // hash remaining bytes
 184   if (n) {
 185     k1 *= C1;
 186     k1 = (k1<<15)|(k1>>(32-15));
 187     k1 *= C2;
 188     hash ^= k1;
 189   }
 190   hash ^= len;
 191
 192   // fmix
 193   hash ^= hash>>16;
 194   hash *= 0x85ebca6bu;
 195   hash ^= hash>>13;
 196   hash *= 0xc2b2ae35u;
 197   hash ^= hash>>16;
 198   return hash;
 199 }
 200
 201
 202 version(iv_vfs_hash_test) unittest {
 203   assert(mur3HashOf("Sample string") == 216753265u);
 204   assert(mur3HashOf("Alice & Miriel") == 694007271u);
 205
 206   static struct StringRange {
 207     const(char)[] s;
 208     usize pos;
 209   pure nothrow @trusted @nogc:
 210     this (const(char)[] as) { s = as; pos = 0; }
 211     @property bool empty () const { return (pos >= s.length); }
 212     @property ubyte front () const { return (pos < s.length ? cast(ubyte)s.ptr[pos] : 0); }
 213     void popFront () { if (pos < s.length) ++pos; }
 214   }
 215
 216   assert(mur3HashOf(StringRange("Sample string")) == 216753265u);
 217   assert(mur3HashOf(StringRange("Alice & Miriel")) == 694007271u);
 218 }
 219
 220
 221 // ////////////////////////////////////////////////////////////////////////// //
 222 version(Posix) {
 223   private extern(C) char* secure_getenv (const(char)* name) nothrow @trusted @nogc;
 224 }
 225
 226 // ////////////////////////////////////////////////////////////////////////// //
 227 /// get user's home path (always terminated with '/'). if `username` is `null`, use current user name.
 228 /// returns path in `destBuf` or `null` if there is no room in `destBuf`.
 229 public char[] getUserHomePath (char[] destBuf, const(char)[] username=null) nothrow @trusted @nogc {
 230   if (destBuf.length == 0) return null;
 231
 232   char[] putAsciiz (const(char)* s) nothrow @trusted @nogc {
 233     import core.stdc.string : strlen;
 234     assert(s !is null && s[0]);
 235     auto slen = strlen(s);
 236     if (destBuf.length < slen+(s[slen-1] == '/' ? 0 : 1)) return null; // oops
 237     destBuf[0..slen] = s[0..slen];
 238     if (s[slen-1] != '/') destBuf[slen] = '/';
 239     return destBuf[0..slen+(s[slen-1] == '/' ? 0 : 1)];
 240   }
 241
 242   version(Posix) {
 243     import core.stdc.errno : errno, ERANGE;
 244     import core.stdc.stdlib : free, malloc, realloc/*, getenv*/;
 245     import core.sys.posix.pwd : passwd, getpwnam_r, getpwuid_r;
 246     import core.sys.posix.unistd : geteuid;
 247     import core.sys.posix.sys.types : uid_t;
 248
 249     uid_t euid;
 250     char* unamez = null; // asciiz username; if null, use euid
 251     scope(exit) if (unamez !is null) free(unamez);
 252
 253     // default user
 254     if (username.length == 0) {
 255       // try $HOME first
 256       auto homedir = secure_getenv("HOME");
 257       if (homedir !is null && homedir[0]) return putAsciiz(homedir);
 258       // no $HOME, get effectife user id
 259       euid = geteuid();
 260     } else {
 261       // ok, we have user name
 262       unamez = cast(char*)malloc(username.length+1);
 263       if (unamez is null) assert(0, "out of memory in `getUserHomePath()`");
 264       unamez[0..username.length+1] = 0;
 265       unamez[0..username.length] = username[];
 266     }
 267
 268     // Reserve C memory for the getpwnam_r() function.
 269     uint infoBufSize = 5 * 1024;
 270     char* infoBuf = null;
 271     scope(exit) if (infoBuf !is null) free(infoBuf);
 272
 273     passwd result;
 274     for (;;) {
 275       infoBuf = cast(char*)realloc(infoBuf, infoBufSize*char.sizeof);
 276       if (infoBuf is null) assert(0, "out of memory in `getUserHomePath()`");
 277       passwd* verify = null;
 278       errno = 0;
 279       auto xres = (unamez !is null ?
 280         getpwnam_r(unamez, &result, infoBuf, infoBufSize, &verify) :
 281         getpwuid_r(euid, &result, infoBuf, infoBufSize, &verify));
 282       if (xres == 0) {
 283         // succeeded if verify points at result
 284         if (verify == &result) {
 285           if (result.pw_dir !is null && result.pw_dir[0]) return putAsciiz(result.pw_dir);
 286           return putAsciiz("./"); // last resort
 287         }
 288       }
 289       if (errno != ERANGE && errno != 0) assert(0, "out of memory in `getUserHomePath()`");
 290       import core.checkedint : mulu;
 291       bool overflow;
 292       infoBufSize = mulu(infoBufSize, 2, overflow);
 293       if (overflow) assert(0);
 294     }
 295     assert(0, "wtf?!");
 296   } else {
 297     return putAsciiz("./"); // nobody cares
 298   }
 299 }
 300
 301
 302 // ////////////////////////////////////////////////////////////////////////// //
 303 /// expands '~...' path to real path.
 304 /// returns new path in `destBuf` or `null` if there is no room in `destBuf`.
 305 /// `destBuf` cannot be the same as `inputPath`!
 306 public char[] expandTilde (char[] destBuf, const(char)[] inputPath) nothrow @trusted @nogc {
 307   if (destBuf.length == 0) {
 308     if (inputPath.length == 0) return destBuf;
 309     if (destBuf.length < inputPath.length) return null; // no room anyway
 310     assert(destBuf.ptr !is inputPath.ptr); // just in case
 311   }
 312
 313   if (inputPath[0] != '~') {
 314     // nothing to do
 315     destBuf[0..inputPath.length] = inputPath[];
 316     version(Posix) {} else {
 317       foreach (ref char ch; destBuf[0..inputPath.length]) if (ch == '\\') ch = '/';
 318       //if (inputPath.length > 2 && inputPath[1] == ':' && inputPath[2] == '/') destBuf[2] = '\\';
 319     }
 320     return destBuf[0..inputPath.length];
 321   }
 322
 323   usize pathpos = 1;
 324   version(Posix) {
 325     while (pathpos < inputPath.length && inputPath.ptr[pathpos] != '/') ++pathpos;
 326   } else {
 327     while (pathpos < inputPath.length && inputPath.ptr[pathpos] != '/' && inputPath.ptr[pathpos] != '\\') ++pathpos;
 328   }
 329   const(char)[] uname = inputPath[1..pathpos];
 330   if (pathpos < inputPath.length) { assert(inputPath[pathpos] == '/' || inputPath[pathpos] == '\\'); ++pathpos; }
 331   // put path into destDir
 332   auto hp = getUserHomePath(destBuf, uname);
 333   if (hp is null) return null;
 334   // append rest of the path
 335   if (pathpos >= inputPath.length) return hp;
 336   immutable irest = inputPath.length-pathpos;
 337   if (destBuf.length-hp.length < irest) return null; // oops, no room
 338   destBuf[hp.length..hp.length+irest] = inputPath[pathpos..$];
 339   version(Posix) {} else {
 340     foreach (ref char ch; destBuf[0..hp.length+irest]) if (ch == '\\') ch = '/';
 341     //if (inputPath.length > 2 && inputPath[1] == ':' && inputPath[2] == '/') destBuf[2] = '\\';
 342   }
 343   return destBuf[0..hp.length+irest];
 344 }
 345
 346
 347 // ////////////////////////////////////////////////////////////////////////// //
 348 inout(char)[] removeExtension (inout(char)[] fn) pure nothrow @trusted @nogc {
 349   foreach_reverse (immutable cidx, char ch; fn) {
 350     version(Posix) {
 351       if (ch == '/') break;
 352     } else {
 353       if (ch == '/' || ch == '\\' || ch == ':') break;
 354     }
 355     if (ch == '.') { fn = fn[0..cidx]; break; }
 356   }
 357   return fn;
 358 }
 359
 360
 361 inout(char)[] getExtension (inout(char)[] fn) pure nothrow @trusted @nogc {
 362   foreach_reverse (immutable cidx, char ch; fn) {
 363     version(Posix) {
 364       if (ch == '/') return null;
 365     } else {
 366       if (ch == '/' || ch == '\\' || ch == ':') return null;
 367     }
 368     if (ch == '.') {
 369       if (cidx == fn.length) return null;
 370       return fn[cidx..$];
 371     }
 372   }
 373   return null;
 374 }
 375
 376
 377 inout(char)[] baseName (inout(char)[] fn) pure nothrow @trusted @nogc {
 378   foreach_reverse (immutable cidx, char ch; fn) {
 379     version(Posix) {
 380       if (ch == '/') return fn[cidx+1..$];
 381     } else {
 382       if (ch == '/' || ch == '\\' || ch == ':') return fn[cidx+1..$];
 383     }
 384   }
 385   return fn;
 386 }
 387
 388
 389 // without last '/' (if it is not a root dir)
 390 // also, returns null if there is no dir (not ".")
 391 inout(char)[] dirName (inout(char)[] fn) pure nothrow @trusted @nogc {
 392   foreach_reverse (immutable cidx, char ch; fn) {
 393     version(Posix) {
 394       if (ch == '/') return (cidx != 0 ? fn[0..cidx] : fn[0..1]);
 395     } else {
 396       // this is wrong, but idc
 397       if (ch == '/' || ch == '\\' || ch == ':') return fn[0..cidx];
 398     }
 399   }
 400   return null;
 401 }