From patchwork Sun Jun 25 21:02:09 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 9808393 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 944306088A for ; Sun, 25 Jun 2017 21:02:36 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 84A24280CF for ; Sun, 25 Jun 2017 21:02:36 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7922B281F9; Sun, 25 Jun 2017 21:02:36 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D6C56280DE for ; Sun, 25 Jun 2017 21:02:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751368AbdFYVCY (ORCPT ); Sun, 25 Jun 2017 17:02:24 -0400 Received: from mail-wr0-f196.google.com ([209.85.128.196]:33638 "EHLO mail-wr0-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751359AbdFYVCW (ORCPT ); Sun, 25 Jun 2017 17:02:22 -0400 Received: by mail-wr0-f196.google.com with SMTP id x23so26437938wrb.0 for ; Sun, 25 Jun 2017 14:02:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=pNsMexpBRqs15GYkbosCsg+0NolFbHylNWsQZpx8svE=; b=Bu2JALo9VPcvOYZgIvd/zzQAmdWx1turA7XiEJSP4nopedHpxLBgVEuDzK+H1XrxWT LOV3zkfKuPp5n6n1Vbd4yForMFTcsseFO/UiBYqKsxxJM1Ua2pjK/mw+dH3SUD3AOygY 12WpCQQ4OhnhytnmAYf1toHsFB/YSUReJURkUB9tRY9KP3wgw3jUw7Vm6pjpYThQ8s51 YT6LHS5nN9M8779JDddp3cSykpCfiJ40VPQMXlSiIK+W2OupRfzAb54tK5FcYJKN9utE SKjy9AxrQ0u3NAWo8u9yYZfEg6rG1on9bvJSM7hin/k77OLnjvYn1FBdGZuVh3o3Vm0i fYOg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=pNsMexpBRqs15GYkbosCsg+0NolFbHylNWsQZpx8svE=; b=TwV06ogX3hv57hQeV+tiCC4qS3gwwWP8kBNyu7UlL8TbzqWlM1MhQ2/5Wha3gkW3Vk 3wv8dzgPLgs7dH/32PzjOmmBCe5TkzCWbh2JFp8idyGyzH9z3iA52me429iQdWG9n+Rf OB8BKxIlEAnZ1qR8+dJLqAlS+CrU2OgYOpqYBlLUUfI4BwhMt7NjbRLF/hXYz1NjzvfX 4G2jDkNlhoZ1S+NAB51uAk611ujRIaKnvlFPylCaO0OgtUdGdb1AJk9UTNrF9OCamLhi Mwi+65jNIlILIztFYEOjnQL3Ax+cpNdXwvNuC3CBsSWE2Nbq4D1fTKRJsGB9DirjgkJl GLqg== X-Gm-Message-State: AKS2vOy22W1jkEg8SXKn7mKbm5tXyC7xpji9Du2sApaAYKe3DaWI8HiP bNHyPjZjOqq9U7Ii X-Received: by 10.28.26.2 with SMTP id a2mr11293227wma.32.1498424540790; Sun, 25 Jun 2017 14:02:20 -0700 (PDT) Received: from titovetst-beplan.itransition.corp (nat3-minsk-pool-46-53-180-190.telecom.by. [46.53.180.190]) by smtp.gmail.com with ESMTPSA id d91sm4915852wma.7.2017.06.25.14.02.19 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 25 Jun 2017 14:02:19 -0700 (PDT) From: Timofey Titovets To: linux-btrfs@vger.kernel.org Cc: Timofey Titovets Subject: [RFC PATCH 1/2] Btrfs: add precomputed log2() Date: Mon, 26 Jun 2017 00:02:09 +0300 Message-Id: <20170625210210.24383-2-nefelim4ag@gmail.com> X-Mailer: git-send-email 2.13.1 In-Reply-To: <20170625210210.24383-1-nefelim4ag@gmail.com> References: <20170625210210.24383-1-nefelim4ag@gmail.com> Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 | 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 -- 2.13.1 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html 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);