From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm0-f67.google.com ([74.125.82.67]:35764 "EHLO mail-wm0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751890AbdGAQ4Q (ORCPT ); Sat, 1 Jul 2017 12:56:16 -0400 Received: by mail-wm0-f67.google.com with SMTP id u23so13092148wma.2 for ; Sat, 01 Jul 2017 09:56:16 -0700 (PDT) From: Timofey Titovets To: linux-btrfs@vger.kernel.org Cc: Timofey Titovets Subject: [RFC PATCH v4 1/2] Btrfs: add precomputed log2() Date: Sat, 1 Jul 2017 19:56:01 +0300 Message-Id: <20170701165602.31189-2-nefelim4ag@gmail.com> In-Reply-To: <20170701165602.31189-1-nefelim4ag@gmail.com> References: <20170701165602.31189-1-nefelim4ag@gmail.com> Sender: linux-btrfs-owner@vger.kernel.org List-ID: Heuristic code compute shannon entropy in cases when other methods can't make clear decision For realization that calculation it's needs floating point, but as this doesn't possible to use floating point, lets just precalculate all our input/output values Signed-off-by: Timofey Titovets --- fs/btrfs/log2_lshift16.c | 278 +++++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/log2_lshift16.h | 11 ++ 2 files changed, 289 insertions(+) create mode 100644 fs/btrfs/log2_lshift16.c create mode 100644 fs/btrfs/log2_lshift16.h diff --git a/fs/btrfs/log2_lshift16.c b/fs/btrfs/log2_lshift16.c new file mode 100644 index 000000000000..0d5d414b2adf --- /dev/null +++ b/fs/btrfs/log2_lshift16.c @@ -0,0 +1,278 @@ +#include +#include "log2_lshift16.h" + +/* + * Precalculated log2 values + * Shifting used for avoiding floating point + * Fraction must be left shifted by 16 + * Return of log are left shifted by 3 + */ +int log2_lshift16(u64 lshift16) +{ + if (lshift16 < 558) { + if (lshift16 < 54) { + if (lshift16 < 13) { + if (lshift16 < 7) { + if (lshift16 < 1) + return -136; + if (lshift16 < 2) + return -123; + if (lshift16 < 3) + return -117; + if (lshift16 < 4) + return -113; + if (lshift16 < 5) + return -110; + if (lshift16 < 6) + return -108; + if (lshift16 < 7) + return -106; + } else { + if (lshift16 < 8) + return -104; + if (lshift16 < 9) + return -103; + if (lshift16 < 10) + return -102; + if (lshift16 < 11) + return -100; + if (lshift16 < 12) + return -99; + if (lshift16 < 13) + return -98; + } + } else { + if (lshift16 < 29) { + if (lshift16 < 15) + return -97; + if (lshift16 < 16) + return -96; + if (lshift16 < 17) + return -95; + if (lshift16 < 19) + return -94; + if (lshift16 < 21) + return -93; + if (lshift16 < 23) + return -92; + if (lshift16 < 25) + return -91; + if (lshift16 < 27) + return -90; + if (lshift16 < 29) + return -89; + } else { + if (lshift16 < 32) + return -88; + if (lshift16 < 35) + return -87; + if (lshift16 < 38) + return -86; + if (lshift16 < 41) + return -85; + if (lshift16 < 45) + return -84; + if (lshift16 < 49) + return -83; + if (lshift16 < 54) + return -82; + } + } + } else { + if (lshift16 < 181) { + if (lshift16 < 99) { + if (lshift16 < 59) + return -81; + if (lshift16 < 64) + return -80; + if (lshift16 < 70) + return -79; + if (lshift16 < 76) + return -78; + if (lshift16 < 83) + return -77; + if (lshift16 < 91) + return -76; + if (lshift16 < 99) + return -75; + } else { + if (lshift16 < 108) + return -74; + if (lshift16 < 117) + return -73; + if (lshift16 < 128) + return -72; + if (lshift16 < 140) + return -71; + if (lshift16 < 152) + return -70; + if (lshift16 < 166) + return -69; + if (lshift16 < 181) + return -68; + } + } else { + if (lshift16 < 304) { + if (lshift16 < 197) + return -67; + if (lshift16 < 215) + return -66; + if (lshift16 < 235) + return -65; + if (lshift16 < 256) + return -64; + if (lshift16 < 279) + return -63; + if (lshift16 < 304) + return -62; + } else { + if (lshift16 < 332) + return -61; + if (lshift16 < 362) + return -60; + if (lshift16 < 395) + return -59; + if (lshift16 < 431) + return -58; + if (lshift16 < 470) + return -57; + if (lshift16 < 512) + return -56; + if (lshift16 < 558) + return -55; + } + } + } + } else { + if (lshift16 < 6317) { + if (lshift16 < 2048) { + if (lshift16 < 1117) { + if (lshift16 < 609) + return -54; + if (lshift16 < 664) + return -53; + if (lshift16 < 724) + return -52; + if (lshift16 < 790) + return -51; + if (lshift16 < 861) + return -50; + if (lshift16 < 939) + return -49; + if (lshift16 < 1024) + return -48; + if (lshift16 < 1117) + return -47; + } else { + if (lshift16 < 1218) + return -46; + if (lshift16 < 1328) + return -45; + if (lshift16 < 1448) + return -44; + if (lshift16 < 1579) + return -43; + if (lshift16 < 1722) + return -42; + if (lshift16 < 1878) + return -41; + if (lshift16 < 2048) + return -40; + } + } else { + if (lshift16 < 3756) { + if (lshift16 < 2233) + return -39; + if (lshift16 < 2435) + return -38; + if (lshift16 < 2656) + return -37; + if (lshift16 < 2896) + return -36; + if (lshift16 < 3158) + return -35; + if (lshift16 < 3444) + return -34; + if (lshift16 < 3756) + return -33; + } else { + if (lshift16 < 4096) + return -32; + if (lshift16 < 4467) + return -31; + if (lshift16 < 4871) + return -30; + if (lshift16 < 5312) + return -29; + if (lshift16 < 5793) + return -28; + if (lshift16 < 6317) + return -27; + } + } + } else { + if (lshift16 < 21247) { + if (lshift16 < 11585) { + if (lshift16 < 6889) + return -26; + if (lshift16 < 7512) + return -25; + if (lshift16 < 8192) + return -24; + if (lshift16 < 8933) + return -23; + if (lshift16 < 9742) + return -22; + if (lshift16 < 10624) + return -21; + if (lshift16 < 11585) + return -20; + } else { + if (lshift16 < 12634) + return -19; + if (lshift16 < 13777) + return -18; + if (lshift16 < 15024) + return -17; + if (lshift16 < 16384) + return -16; + if (lshift16 < 17867) + return -15; + if (lshift16 < 19484) + return -14; + if (lshift16 < 21247) + return -13; + } + } else { + if (lshift16 < 35734) { + if (lshift16 < 23170) + return -12; + if (lshift16 < 25268) + return -11; + if (lshift16 < 27554) + return -10; + if (lshift16 < 30048) + return -9; + if (lshift16 < 32768) + return -8; + if (lshift16 < 35734) + return -7; + } else { + if (lshift16 < 38968) + return -6; + if (lshift16 < 42495) + return -5; + if (lshift16 < 46341) + return -4; + if (lshift16 < 50535) + return -3; + if (lshift16 < 55109) + return -2; + if (lshift16 < 60097) + return -1; + } + } + } + } + return 0; +} diff --git a/fs/btrfs/log2_lshift16.h b/fs/btrfs/log2_lshift16.h new file mode 100644 index 000000000000..fba434e3984a --- /dev/null +++ b/fs/btrfs/log2_lshift16.h @@ -0,0 +1,11 @@ +#include +/* + * Precalculated log2 values + * Shifting used for avoiding floating point + * Fraction must be left shifted by 16 + * Return of log are left shifted by 3 + */ + +#define LOG2_ARG_SHIFT (1 << 16) +#define LOG2_RET_SHIFT (1 << 3) +int log2_lshift16(u64 lshift16); -- 2.13.2