12bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan/* ===-- clzsi2.c - Implement __clzsi2 -------------------------------------=== 22bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * 31c5f89b1dd741135a4007ab577723d422f421eecAnton Korobeynikov * The LLVM Compiler Infrastructure 42bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * 59ad441ffec97db647fee3725b3424284fb913e14Howard Hinnant * This file is dual licensed under the MIT and the University of Illinois Open 69ad441ffec97db647fee3725b3424284fb913e14Howard Hinnant * Source Licenses. See LICENSE.TXT for details. 72bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * 82bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * ===----------------------------------------------------------------------=== 92bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * 102bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * This file implements __clzsi2 for the compiler_rt library. 112bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * 122bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * ===----------------------------------------------------------------------=== 132bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan */ 14b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 15b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar#include "int_lib.h" 16b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 172bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan/* Returns: the number of leading 0-bits */ 18b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 192bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan/* Precondition: a != 0 */ 20b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 211c5f89b1dd741135a4007ab577723d422f421eecAnton KorobeynikovCOMPILER_RT_ABI si_int 22b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar__clzsi2(si_int a) 23b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar{ 24b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar su_int x = (su_int)a; 252bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan si_int t = ((x & 0xFFFF0000) == 0) << 4; /* if (x is small) t = 16 else 0 */ 262bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan x >>= 16 - t; /* x = [0 - 0xFFFF] */ 272bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan su_int r = t; /* r = [0, 16] */ 282bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan /* return r + clz(x) */ 29b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar t = ((x & 0xFF00) == 0) << 3; 302bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan x >>= 8 - t; /* x = [0 - 0xFF] */ 312bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan r += t; /* r = [0, 8, 16, 24] */ 322bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan /* return r + clz(x) */ 33b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar t = ((x & 0xF0) == 0) << 2; 342bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan x >>= 4 - t; /* x = [0 - 0xF] */ 352bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan r += t; /* r = [0, 4, 8, 12, 16, 20, 24, 28] */ 362bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan /* return r + clz(x) */ 37b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar t = ((x & 0xC) == 0) << 1; 382bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan x >>= 2 - t; /* x = [0 - 3] */ 392bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan r += t; /* r = [0 - 30] and is even */ 402bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan /* return r + clz(x) */ 412bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan/* switch (x) 422bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * { 432bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * case 0: 442bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * return r + 2; 452bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * case 1: 462bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * return r + 1; 472bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * case 2: 482bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * case 3: 492bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * return r; 502bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan * } 512bf62728b8ce00e295c7bf0fb328427496cc85aaEdward O'Callaghan */ 52b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return r + ((2 - x) & -((x & 2) == 0)); 53b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar} 54