yaffs: Refactor bit counting code

For Linux kernel we use hweight8() and hweight32(). This allows
use of special bit-counting code instructions in processors that
do this.

The yaffs direct we now only use one set of code. There were two.

NB On x86 the yaffs hweight8 code is actually a lot faster
than the sofwtare implementation in Linux kernel.

Signed-off-by: Charles Manning <cdhmanning@gmail.com>

diff --git a/direct/basic-test/Makefile b/direct/basic-test/Makefile
index cc9094e647b13d01f557686dcb6ffdd764594421..214f4e925ce868f8d3c07d05a98194f478a6055e 100644 (file)
--- a/direct/basic-test/Makefile
+++ b/direct/basic-test/Makefile
@@ -33,7 +33,7 @@ CFLAGS+=   -Werror=undef
 CFLAGS+=   -DCONFIG_YAFFS_USE_PTHREADS -lpthread
 
 
-COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o \
+COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o \
                 yaffs_ecc.o yaffs_fileem.o yaffs_fileem2k.o yaffsfs.o yaffs_guts.o \
                 yaffs_packedtags1.o yaffs_ramdisk.o yaffs_ramem2k.o \
                 yaffs_tagscompat.o yaffs_packedtags2.o yaffs_tagsvalidity.o yaffs_nand.o \
@@ -65,7 +65,8 @@ YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffs_flashif.h yaffs_flashif2.h\
                       yaffsfs.h yaffs_osglue.h ydirectenv.h \
                       yaffs_flashif.c yaffscfg.h yaffs_list.h \
                       yaffs_qsort.c yportenv.h yaffs_attribs.c \
-                      yaffs_nandif.c yaffs_nandif.h yaffs_nandemul2k.h
+                      yaffs_nandif.c yaffs_nandif.h yaffs_nandemul2k.h \
+                      yaffs_hweight.h yaffs_hweight.c \
 
 
 

diff --git a/direct/python/Makefile b/direct/python/Makefile
index ad5b47f5d51b1c468321d3ca91ca55a1a9311af0..6e0c5fd0baa6a21f029896ef10c7d55891858b7e 100644 (file)
--- a/direct/python/Makefile
+++ b/direct/python/Makefile
@@ -29,7 +29,7 @@ CFLAGS +=    -O0 -fPIC
 #CFLAGS+=   -Wmissing-prototypes -Wredundant-decls -Wnested-externs -Winline
 
 
-COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o \
+COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o\
                 yramsim.o yaffs_fileem2k.o\
                 yaffs_nandif.o yaffs_attribs.o \
                 yaffsfs.o  yaffs_ecc.o yaffs_guts.o \
@@ -64,7 +64,8 @@ YAFFSSYMLINKS = yaffs_ecc.c yaffs_ecc.h yaffs_guts.c yaffs_guts.h yaffs_tagscomp
 YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffsfs.h yaffscfg.h yaffs_osglue.h  ydirectenv.h \
                       yaffs_flashif.c yaffs_flashif.h yaffs_flashif2.h yaffs_list.h \
                       yaffs_nandif.c yaffs_nandif.h yaffs_qsort.c yaffs_nandemul2k.h \
-                      yportenv.h yaffs_attribs.c
+                      yportenv.h yaffs_attribs.c \
+                      yaffs_hweight.c yaffs_hweight.h
 
 DIRECTEXTRASYMLINKS =   yaffscfg2k.c yaffs_fileem2k.c yaffs_fileem2k.h\
                         yaffs_fileem.c yaffs_norif1.c yaffs_norif1.h \

diff --git a/direct/tests/Makefile b/direct/tests/Makefile
index bbeb8de68e2d76308b702c57edfda34fe53a0903..00db67d715ebf16f4c113cd034ec37723b3c10cd 100644 (file)
--- a/direct/tests/Makefile
+++ b/direct/tests/Makefile
@@ -30,7 +30,7 @@ CFLAGS +=    -Wextra -Wpointer-arith
 #CFLAGS+=   -Wmissing-prototypes -Wredundant-decls -Wnested-externs -Winline
 
 
-COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o \
+COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o\
                 yaffs_ecc.o yaffs_fileem.o yaffs_fileem2k.o yaffsfs.o yaffs_guts.o \
                 yaffs_packedtags1.o yaffs_ramdisk.o yaffs_ramem2k.o \
                 yaffs_tagscompat.o yaffs_packedtags2.o yaffs_tagsvalidity.o yaffs_nand.o \
@@ -67,7 +67,8 @@ YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffs_flashif.h yaffs_flashif2.h\
                       yaffs_flashif.c yaffscfg.h yaffs_qsort.c \
                       yaffs_nandemul2k.h yaffs_list.h \
                       yaffs_attribs.c \
-                      yaffs_nandif.c yaffs_nandif.h yportenv.h
+                      yaffs_nandif.c yaffs_nandif.h yportenv.h \
+                      yaffs_hweight.c yaffs_hweight.h
 
 
 DIRECTEXTRASYMLINKS =  yaffscfg2k.c yaffs_fileem2k.c yaffs_fileem2k.h\

diff --git a/direct/timothy_tests/quick_tests/Makefile b/direct/timothy_tests/quick_tests/Makefile
index 1d8a0259250b5193ea7ad2dca8f28cc50eb59462..6001261a5cd28fc9fc07b751c7858b255308d03b 100644 (file)
--- a/direct/timothy_tests/quick_tests/Makefile
+++ b/direct/timothy_tests/quick_tests/Makefile
@@ -30,7 +30,7 @@ CFLAGS +=    -Wextra -Wpointer-arith
 #CFLAGS+=   -Wmissing-prototypes -Wredundant-decls -Wnested-externs -Winline
 
 
-COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o \
+COMMONTESTOBJS = yaffscfg2k.o yaffs_osglue.o yaffs_hweight.o \
                 yaffs_ecc.o yaffs_fileem.o yaffs_fileem2k.o yaffsfs.o yaffs_guts.o \
                 yaffs_packedtags1.o yaffs_ramdisk.o yaffs_ramem2k.o \
                 yaffs_tagscompat.o yaffs_packedtags2.o yaffs_tagsvalidity.o yaffs_nand.o \
@@ -125,7 +125,8 @@ YAFFSDIRECTSYMLINKS =  yaffsfs.c yaffs_flashif.h yaffs_flashif2.h\
                       yaffs_flashif.c yaffscfg.h yaffs_qsort.c \
                       yaffs_nandemul2k.h yaffs_list.h \
                       yaffs_attribs.c yaffs_osglue.h \
-                      yaffs_nandif.c yaffs_nandif.h yportenv.h
+                      yaffs_nandif.c yaffs_nandif.h yportenv.h \
+                      yaffs_hweight.h yaffs_hweight.c
 
 
 DIRECTEXTRASYMLINKS =  yaffscfg2k.c yaffs_fileem2k.c yaffs_fileem2k.h\

diff --git a/direct/yaffs_hweight.c b/direct/yaffs_hweight.c
new file mode 100644 (file)
index 0000000..d283b87
--- /dev/null
+++ b/direct/yaffs_hweight.c
@@ -0,0 +1,53 @@
+/*
+ * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
+ *
+ * Copyright (C) 2002-2010 Aleph One Ltd.
+ *   for Toby Churchill Ltd and Brightstar Engineering
+ *
+ * Created by Charles Manning <charles@aleph1.co.uk>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+ 
+ /* These functions have been renamed to hweightxx to match the
+  * equivaqlent functions in the Linux kernel.
+  */
+
+#include "yaffs_hweight.h"
+
+static const char yaffs_count_bits_table[256] = {
+       0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+       4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+};
+
+int yaffs_hweight8(u8 x)
+{
+       int ret_val;
+       ret_val = yaffs_count_bits_table[x];
+       return ret_val;
+}
+
+int yaffs_hweight32(u32 x)
+{
+       return hweight8(x & 0xff) + 
+               hweight8((x >> 8) & 0xff) +
+               hweight8((x >> 16) & 0xff) +
+               hweight8((x >> 24) & 0xff);
+}
+

diff --git a/direct/yaffs_hweight.h b/direct/yaffs_hweight.h
new file mode 100644 (file)
index 0000000..cfe38dd
--- /dev/null
+++ b/direct/yaffs_hweight.h
@@ -0,0 +1,24 @@
+/*
+ * YAFFS: Yet another Flash File System . A NAND-flash specific file system. 
+ *
+ * Copyright (C) 2002-2010 Aleph One Ltd.
+ *   for Toby Churchill Ltd and Brightstar Engineering
+ *
+ * Created by Charles Manning <charles@aleph1.co.uk>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 2.1 as
+ * published by the Free Software Foundation.
+ *
+ * Note: Only YAFFS headers are LGPL, YAFFS C code is covered by GPL.
+ */
+
+#ifndef __YAFFS_HWEIGHT_H__
+#define __YAFFS_HWEIGHT_H__
+
+#include "yportenv.h"
+
+int yaffs_hweight8(u8 x);
+int yaffs_hweight32(u32 x);
+
+#endif

diff --git a/direct/ydirectenv.h b/direct/ydirectenv.h
index be80e68c9eec74d2d1653681821db87a3da88b10..ceaa6c8423e1a4fad573c5215815d9a31817ea0f 100644 (file)
--- a/direct/ydirectenv.h
+++ b/direct/ydirectenv.h
@@ -26,6 +26,7 @@
 #include "stdio.h"
 #include "string.h"
 #include "yaffs_osglue.h"
+#include "yaffs_hweight.h"
 
 #include "assert.h"
 #define YBUG() assert(0)
@@ -43,6 +44,9 @@
 #define yaffs_sprintf       sprintf
 #define yaffs_toupper(a)     toupper(a)
 
+#define hweight8(x)    yaffs_hweight8(x)
+#define hweight32(x)   yaffs_hweight32(x)
+
 void yaffs_qsort(void *aa, size_t n, size_t es,
         int (*cmp)(const void *, const void *));
 
@@ -94,7 +98,6 @@ void yaffs_qsort(void *aa, size_t n, size_t es,
 
 #include "yaffs_list.h"
 
-
 #include "yaffsfs.h"
 
 #endif

diff --git a/yaffs_ecc.c b/yaffs_ecc.c
index 0ea0305e5ceb10025f9e4016c439930631ac9a79..e95a8069a8c5bc0c754b9f41ddbc9944e0b76f98 100644 (file)
--- a/yaffs_ecc.c
+++ b/yaffs_ecc.c
@@ -67,29 +67,6 @@ static const unsigned char column_parity_table[] = {
        0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
 };
 
-/* Count the bits in an unsigned char or a U32 */
-
-static int yaffs_count_bits(unsigned char x)
-{
-       int r = 0;
-       while (x) {
-               if (x & 1)
-                       r++;
-               x >>= 1;
-       }
-       return r;
-}
-
-static int yaffs_count_bits32(unsigned x)
-{
-       int r = 0;
-       while (x) {
-               if (x & 1)
-                       r++;
-               x >>= 1;
-       }
-       return r;
-}
 
 /* Calculate the ECC for a 256-byte block of data */
 void yaffs_ecc_cacl(const unsigned char *data, unsigned char *ecc)
@@ -222,8 +199,7 @@ int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc,
                return 1;       /* Corrected the error */
        }
 
-       if ((yaffs_count_bits(d0) +
-            yaffs_count_bits(d1) + yaffs_count_bits(d2)) == 1) {
+       if ((hweight8(d0) + hweight8(d1) + hweight8(d2)) == 1) {
                /* Reccoverable error in ecc */
 
                read_ecc[0] = test_ecc[0];
@@ -307,9 +283,9 @@ int yaffs_ecc_correct_other(unsigned char *data, unsigned n_bytes,
                return 1;       /* corrected */
        }
 
-       if ((yaffs_count_bits32(delta_line) +
-            yaffs_count_bits32(delta_line_prime) +
-            yaffs_count_bits(delta_col)) == 1) {
+       if ((hweight32(delta_line) +
+            hweight32(delta_line_prime) +
+            hweight8(delta_col)) == 1) {
                /* Reccoverable error in ecc */
 
                *read_ecc = *test_ecc;

diff --git a/yaffs_tagscompat.c b/yaffs_tagscompat.c
index 3a9a157e7e2470c44252cb338363347db7b04569..a35e0f312171d236549aa134ff4ff2bdee15d892 100644 (file)
--- a/yaffs_tagscompat.c
+++ b/yaffs_tagscompat.c
@@ -19,31 +19,6 @@
 
 static void yaffs_handle_rd_data_error(struct yaffs_dev *dev, int nand_chunk);
 
-static const char yaffs_count_bits_table[256] = {
-       0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
-       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-       2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-       3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-       4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
-};
-
-int yaffs_count_bits(u8 x)
-{
-       int ret_val;
-       ret_val = yaffs_count_bits_table[x];
-       return ret_val;
-}
 
 /********** Tags ECC calculations  *********/
 
@@ -370,7 +345,7 @@ int yaffs_tags_compat_rd(struct yaffs_dev *dev,
                if (ext_tags) {
 
                        int deleted =
-                           (yaffs_count_bits(spare.page_status) < 7) ? 1 : 0;
+                           (hweight8(spare.page_status) < 7) ? 1 : 0;
 
                        ext_tags->is_deleted = deleted;
                        ext_tags->ecc_result = ecc_result;
@@ -443,7 +418,7 @@ int yaffs_tags_compat_query_block(struct yaffs_dev *dev,
        yaffs_rd_chunk_nand(dev, block_no * dev->param.chunks_per_block + 1,
                            NULL, &spare1, &dummy, 1);
 
-       if (yaffs_count_bits(spare0.block_status & spare1.block_status) < 7)
+       if (hweight8(spare0.block_status & spare1.block_status) < 7)
                *state = YAFFS_BLOCK_STATE_DEAD;
        else if (memcmp(&spare_ff, &spare0, sizeof(spare_ff)) == 0)
                *state = YAFFS_BLOCK_STATE_EMPTY;

diff --git a/yportenv_multi.h b/yportenv_multi.h
index ec43fd588db3a7ee40041f58ab0aabcbfd2a7281..4b058a7ff3f7b3fe4a262d4b4359ddeca1df5f12 100644 (file)
--- a/yportenv_multi.h
+++ b/yportenv_multi.h
@@ -53,6 +53,7 @@
 #include <linux/fs.h>
 #include <linux/stat.h>
 #include <linux/sort.h>
+#include <linux/bitops.h>
 
 #define YCHAR char
 #define YUCHAR unsigned char

diff --git a/yportenv_single.h b/yportenv_single.h
index 2eae429a9410ceafabef3f72f9f3f88495c55b07..8fd0da57d595014bf874a146d850ddce35168c17 100644 (file)
--- a/yportenv_single.h
+++ b/yportenv_single.h
@@ -29,6 +29,7 @@
 #include <linux/fs.h>
 #include <linux/stat.h>
 #include <linux/sort.h>
+#include <linux/bitops.h>
 
 #define YCHAR char
 #define YUCHAR unsigned char