]> git.baikalelectronics.ru Git - kernel.git/commit
Btrfs: heuristic: add Shannon entropy calculation
authorTimofey Titovets <nefelim4ag@gmail.com>
Sun, 8 Oct 2017 13:11:59 +0000 (16:11 +0300)
committerDavid Sterba <dsterba@suse.com>
Wed, 1 Nov 2017 19:45:36 +0000 (20:45 +0100)
commit2fea6214f72d0a8d9e904f82d72ae051f1301f19
tree46dd57e47b8378576f60e777887ca7bac729a9c9
parentbb5b3dfd4b045f7fa9dd820a2321dde1fe0e4230
Btrfs: heuristic: add Shannon entropy calculation

Byte distribution check in heuristic will filter edge data cases and
some time fail to classify input data.

Let's fix that by adding Shannon entropy calculation, that will cover
classification of most other data types.

As Shannon entropy needs log2 with some precision to work, let's use
ilog2(N) and for increased precision, by do ilog2(pow(N, 4)).

Shannon entropy has been slightly changed to avoid signed numbers and
division.

The calculation is direct by the formula, successor of precalculated
table or chains of if-else.

The accuracy errors of ilog2 are compensated by

@ENTROPY_LVL_ACEPTABLE 70 -> 65
@ENTROPY_LVL_HIGH      85 -> 80

Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
Reviewed-by: David Sterba <dsterba@suse.com>
[ update comments ]
Signed-off-by: David Sterba <dsterba@suse.com>
fs/btrfs/compression.c