From: Timofey Titovets <nefelim4ag@gmail.com>
To: linux-btrfs@vger.kernel.org
Cc: Timofey Titovets <nefelim4ag@gmail.com>
Subject: [RFC PATCH 1/2] Btrfs: add precomputed log2()
Date: Mon, 26 Jun 2017 00:02:09 +0300 [thread overview]
Message-ID: <20170625210210.24383-2-nefelim4ag@gmail.com> (raw)
In-Reply-To: <20170625210210.24383-1-nefelim4ag@gmail.com>
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 <nefelim4ag@gmail.com>
---
fs/btrfs/log2_lshift16.c | 232 +++++++++++++++++++++++++++++++++++++++++++++++
fs/btrfs/log2_lshift16.h | 10 ++
2 files changed, 242 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..123eb5e8d057
--- /dev/null
+++ b/fs/btrfs/log2_lshift16.c
@@ -0,0 +1,232 @@
+#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(long long unsigned lshift16)
+{
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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;
+ 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..ca16aa36e3ea
--- /dev/null
+++ b/fs/btrfs/log2_lshift16.h
@@ -0,0 +1,10 @@
+/*
+ * 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(long long unsigned lshift16);
--
2.13.1
next prev parent reply other threads:[~2017-06-25 21:02 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-06-25 21:02 [RFC PATCH 0/2] Btrfs: add compression heuristic Timofey Titovets
2017-06-25 21:02 ` Timofey Titovets [this message]
2017-06-25 22:31 ` [RFC PATCH 1/2] Btrfs: add precomputed log2() Adam Borowski
2017-06-25 21:02 ` [RFC PATCH 2/2] Btrfs: add heuristic method for make decision compress or not compress Timofey Titovets
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170625210210.24383-2-nefelim4ag@gmail.com \
--to=nefelim4ag@gmail.com \
--cc=linux-btrfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).