From c27a0d75b33c030965cc97d3d7f571107a673fb4 Mon Sep 17 00:00:00 2001 From: Bryan O'Sullivan Date: Wed, 1 Feb 2006 03:05:16 -0800 Subject: [PATCH] Introduce __iowrite32_copy This arch-independent routine copies data to a memory-mapped I/O region, using 32-bit accesses. The naming is double-underscored to make it clear that it does not guarantee write ordering, nor does it perform a memory barrier afterwards; the kernel doc also explicitly states this. This style of access is required by some devices. This change also introduces include/linux/io.h, at Andrew's suggestion. It only has one occupant at the moment, but is a logical destination for oft-replicated contents of include/asm-*/{io,iomap}.h to migrate to. Signed-off-by: Bryan O'Sullivan Cc: Andi Kleen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/Makefile | 2 +- lib/iomap_copy.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+), 1 deletion(-) create mode 100644 lib/iomap_copy.c (limited to 'lib') diff --git a/lib/Makefile b/lib/Makefile index 8535f4d..648b2c1 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -9,7 +9,7 @@ lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \ lib-y += kobject.o kref.o kobject_uevent.o klist.o -obj-y += sort.o parser.o halfmd4.o +obj-y += sort.o parser.o halfmd4.o iomap_copy.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/iomap_copy.c b/lib/iomap_copy.c new file mode 100644 index 0000000..a6b1e27 --- /dev/null +++ b/lib/iomap_copy.c @@ -0,0 +1,42 @@ +/* + * Copyright 2006 PathScale, Inc. All Rights Reserved. + * + * This file is free software; you can redistribute it and/or modify + * it under the terms of version 2 of the GNU General Public License + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include +#include + +/** + * __iowrite32_copy - copy data to MMIO space, in 32-bit units + * @to: destination, in MMIO space (must be 32-bit aligned) + * @from: source (must be 32-bit aligned) + * @count: number of 32-bit quantities to copy + * + * Copy data from kernel space to MMIO space, in units of 32 bits at a + * time. Order of access is not guaranteed, nor is a memory barrier + * performed afterwards. + */ +void __attribute__((weak)) __iowrite32_copy(void __iomem *to, + const void *from, + size_t count) +{ + u32 __iomem *dst = to; + const u32 *src = from; + const u32 *end = src + count; + + while (src < end) + __raw_writel(*src++, dst++); +} +EXPORT_SYMBOL_GPL(__iowrite32_copy); -- cgit v1.1 From 3f330317ab4973178423aba750d6d0ca5ce0024a Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Thu, 2 Feb 2006 17:15:41 -0800 Subject: [TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore The current logic does not calculate correctly the good shift array: Let x be the pattern that is being searched. Let y be the block of data. The good shift array aligns the segment: x[i+1 ... m-1] = y[i+j+1 ... j+m-1] with its rightmost occurrence in x that fulfils x[i] neq y[i+j]. In previous version, the good shift array for the pattern ANPANMAN is: [1, 8, 3, 8, 8, 8, 8, 8] and should be: [1, 8, 3, 6, 6, 6, 6, 6] Signed-off-by: Pablo Neira Ayuso Signed-off-by: David S. Miller --- lib/ts_bm.c | 40 +++++++++++++++++++++++++--------------- 1 file changed, 25 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/ts_bm.c b/lib/ts_bm.c index 8a8b3a1..c4c1ac5 100644 --- a/lib/ts_bm.c +++ b/lib/ts_bm.c @@ -94,10 +94,28 @@ next: bs = bm->bad_shift[text[shift-i]]; return UINT_MAX; } +static int subpattern(u8 *pattern, int i, int j, int g) +{ + int x = i+g-1, y = j+g-1, ret = 0; + + while(pattern[x--] == pattern[y--]) { + if (y < 0) { + ret = 1; + break; + } + if (--g == 0) { + ret = pattern[i-1] != pattern[j-1]; + break; + } + } + + return ret; +} + static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern, unsigned int len) { - int i, j, ended, l[ASIZE]; + int i, j, g; for (i = 0; i < ASIZE; i++) bm->bad_shift[i] = len; @@ -106,23 +124,15 @@ static void compute_prefix_tbl(struct ts_bm *bm, const u8 *pattern, /* Compute the good shift array, used to match reocurrences * of a subpattern */ - for (i = 1; i < bm->patlen; i++) { - for (j = 0; j < bm->patlen && bm->pattern[bm->patlen - 1 - j] - == bm->pattern[bm->patlen - 1 - i - j]; j++); - l[i] = j; - } - bm->good_shift[0] = 1; for (i = 1; i < bm->patlen; i++) bm->good_shift[i] = bm->patlen; - for (i = bm->patlen - 1; i > 0; i--) - bm->good_shift[l[i]] = i; - ended = 0; - for (i = 0; i < bm->patlen; i++) { - if (l[i] == bm->patlen - 1 - i) - ended = i; - if (ended) - bm->good_shift[i] = ended; + for (i = bm->patlen-1, g = 1; i > 0; g++, i--) { + for (j = i-1; j >= 1-g ; j--) + if (subpattern(bm->pattern, i, j, g)) { + bm->good_shift[g] = bm->patlen-j-g; + break; + } } } -- cgit v1.1 From f0c00257d63463fa9d692e632fae037d6c0e67b0 Mon Sep 17 00:00:00 2001 From: Peter Williams Date: Fri, 3 Feb 2006 03:04:33 -0800 Subject: [PATCH] lib: Fix bug in int_sqrt() for 64 bit longs The implementation of int_sqrt() assumes that longs have 32 bits. On systems that have 64 bit longs this will result in gross errors when the argument to the function is greater than 2^32 - 1 on such systems. I doubt whether any such use is currently made of int_sqrt() but the attached patch fixes the problem anyway. Signed-off-by: Peter Williams Cc: Dave Jones Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/int_sqrt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index a5d2cdc..fd355a9 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -15,7 +15,7 @@ unsigned long int_sqrt(unsigned long x) op = x; res = 0; - one = 1 << 30; + one = 1UL << (BITS_PER_LONG - 2); while (one > op) one >>= 2; -- cgit v1.1