bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2001-2018 Dovecot authors, see the included COPYING file */
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody#include "lib.h"
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek/*
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek * We could use bits_required64() unconditionally, but that's unnecessary
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek * and way more heavy weight on 32-bit systems.
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek */
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek#ifdef _LP64
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek#define BITS_REQUIRED(x) bits_required64(x)
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek#else
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek#define BITS_REQUIRED(x) bits_required32(x)
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek#endif
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodysize_t nearest_power(size_t num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody{
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody i_assert(num <= ((size_t)1 << (CHAR_BIT*sizeof(size_t) - 1)));
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek if (num == 0)
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek return 1;
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek
0dac2f5f0a0f25d8f6b789ba089f1a2d01c529a6Josef 'Jeff' Sipek return 1UL << BITS_REQUIRED(num - 1);
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody}
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody
0913e6eb7b5d87a5323440dc6644f7347c360857Timo Sirainen#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody/* Lucky you, it's all inline intrinsics */
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody#else
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmodyunsigned int bits_required8(uint8_t num)
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody{
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody int ret = 0;
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody if (num > 0xf) { ret += 4; num >>= 4; }
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody if (num > 0x3) { ret += 2; num >>= 2; }
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody num &= ~(num>>1); /* 3->2, else unchanged */
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody return ret + num;
3637a2ad3b2ead17efd5591f73effd3b140d8d2dPhil Carmody}
84f697c5e30565823619abaaeb57164c789d4b66Phil Carmody#endif