All of lore.kernel.org
 help / color / mirror / Atom feed
From: Timofey Titovets <nefelim4ag@gmail.com>
To: linux-btrfs@vger.kernel.org
Cc: Timofey Titovets <nefelim4ag@gmail.com>
Subject: [RFC PATCH v4 1/2] Btrfs: add precomputed log2()
Date: Sat,  1 Jul 2017 19:56:01 +0300	[thread overview]
Message-ID: <20170701165602.31189-2-nefelim4ag@gmail.com> (raw)
In-Reply-To: <20170701165602.31189-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 | 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 <linux/types.h>
+#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 <linux/types.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
+ */
+
+#define LOG2_ARG_SHIFT (1 << 16)
+#define LOG2_RET_SHIFT (1 << 3)
+int log2_lshift16(u64 lshift16);
--
2.13.2

  reply	other threads:[~2017-07-01 16:56 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-07-01 16:56 [RFC PATCH v4 0/2] Btrfs: add compression heuristic Timofey Titovets
2017-07-01 16:56 ` Timofey Titovets [this message]
2017-07-01 16:56 ` [RFC PATCH v4 2/2] Btrfs: add heuristic method for make decision compress or not compress Timofey Titovets
2017-07-03 17:30   ` David Sterba
2017-07-04 11:11     ` Timofey Titovets
2017-07-04 15:25       ` David Sterba
2017-07-03 17:09 ` [RFC PATCH v4 0/2] Btrfs: add compression heuristic David Sterba

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=20170701165602.31189-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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.