user/sven/linux.git/lib/Kconfig, branch v2.6.16.45

[PATCH] lib/crc16: added crc16 algorithm.

2005-09-08T21:41:27Z

Add the crc16 routines, as used by w1 devices. Signed-off-by: Ben Gardner Signed-off-by: Evgeniy Polyakov Signed-off-by: Greg Kroah-Hartman

[LIB]: Make TEXTSEARCH_BM plain tristate like the others

2005-08-29T23:11:11Z

And select it when the relevant modules are enabled. Signed-off-by: David S. Miller

[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2

2005-08-29T23:11:06Z

Attached the implementation of the Boyer-Moore string search algorithm for the new textsearch infrastructure. I've added as well a note about the limitations that this approach presents, as Thomas has remarked. Signed-off-by: Pablo Neira Ayuso Signed-off-by: David S. Miller

[PKT_SCHED]: Make TEXTSEARCH* options only selected.

2005-06-25T00:39:03Z

Do not present these confusing new options to the user unless he picked some facility that makes use of it, such as NET_EMATCH_TEXT. Signed-off-by: David S. Miller

[LIB]: Naive finite state machine based textsearch

2005-06-24T03:59:16Z

A finite state machine consists of n states (struct ts_fsm_token) representing the pattern as a finite automation. The data is read sequentially on a octet basis. Every state token specifies the number of recurrences and the type of value accepted which can be either a specific character or ctype based set of characters. The available type of recurrences include 1, (0|1), [0 n], and [1 n]. The algorithm differs between strict/non-strict mode specyfing whether the pattern has to start at the first octect. Strict mode is enabled by default and can be disabled by inserting TS_FSM_HEAD_IGNORE as the first token in the chain. The runtime performance of the algorithm should be around O(n), however while in strict mode the average runtime can be better. Signed-off-by: Thomas Graf Signed-off-by: David S. Miller

[LIB]: Knuth-Morris-Pratt textsearch algorithm

2005-06-24T03:58:37Z

Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt [1]. Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") [2]. Since the array PI has only m entries, whereas DELTA has O(m|SIGMA|) entries, we save a factor of |SIGMA| in the preprocessing time by computing PI rather than DELTA. [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press [2] See finite automation theory Signed-off-by: Thomas Graf Signed-off-by: David S. Miller

[LIB]: Textsearch infrastructure.

2005-06-24T03:49:30Z

The textsearch infrastructure provides text searching facitilies for both linear and non-linear data. Individual search algorithms are implemented in modules and chosen by the user. Signed-off-by: Thomas Graf Signed-off-by: David S. Miller

[PATCH] ia64 uncached alloc

2005-06-22T01:46:18Z

This patch contains the ia64 uncached page allocator and the generic allocator (genalloc). The uncached allocator was formerly part of the SN2 mspec driver but there are several other users of it so it has been split off from the driver. The generic allocator can be used by device driver to manage special memory etc. The generic allocator is based on the allocator from the sym53c8xx_2 driver. Various users on ia64 needs uncached memory. The SGI SN architecture requires it for inter-partition communication between partitions within a large NUMA cluster. The specific user for this is the XPC code. Another application is large MPI style applications which use it for synchronization, on SN this can be done using special 'fetchop' operations but it also benefits non SN hardware which may use regular uncached memory for this purpose. Performance of doing this through uncached vs cached memory is pretty substantial. This is handled by the mspec driver which I will push out in a seperate patch. Rather than creating a specific allocator for just uncached memory I came up with genalloc which is a generic purpose allocator that can be used by device drivers and other subsystems as they please. For instance to handle onboard device memory. It was derived from the sym53c7xx_2 driver's allocator which is also an example of a potential user (I am refraining from modifying sym2 right now as it seems to have been under fairly heavy development recently). On ia64 memory has various properties within a granule, ie. it isn't safe to access memory as uncached within the same granule as currently has memory accessed in cached mode. The regular system therefore doesn't utilize memory in the lower granules which is mixed in with device PAL code etc. The uncached driver walks the EFI memmap and pulls out the spill uncached pages and sticks them into the uncached pool. Only after these chunks have been utilized, will it start converting regular cached memory into uncached memory. Hence the reason for the EFI related code additions. Signed-off-by: Jes Sorensen Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

Shared Reed-Solomon ECC library

2004-10-20T23:55:08Z

The attached patch contains a shared Reed-Solomon Library analogous to the shared zlib. (N)AND FLASH is gaining popularity and there are a lot of ASIC/SoC/FPGA controllers around which implement hardware support for Reed-Solomon error correction. As usual they use different implementations (polynomials etc.). So it's obvious to use a shared library for the common tasks of error correction. A short scan through the kernel revealed that at least the ftape driver uses Reed-Solomon error correction. It could be easily converted to use the shared library code. The encoder/decoder code is lifted from the GPL'd userspace RS-library written by Phil Karn. I modified/wrapped it to provide the different functions which we need in the MTD/NAND code. The library is tested in extenso under various MTD/NAND configurations. The lib should be usable for other purposes right out of the box. Adjustment for currently not implemented functionality is an easy task. I'm willing to take the maintainership of the library. Signed-Off-By: Thomas Gleixner Signed-Off-By: David Woodhouse "No objections at all. Just keep the authorship notices." -- Phil Karn

[PATCH] fix CRC16 misnaming

2004-07-11T02:35:39Z

As pointed by Thomas Sailer, crc16.c module contains CRC16-CCITT (x^16 + x^12 + x^5 + 1) implementation, not IBM CRC16 (x^16 + x^15 + x^2 + 1) one. Looks like we need to rename it accordingly and this patchset does exactly this. Signed-off-by: Andrey Panin Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds