diff options
Diffstat (limited to 'src/Hamming')
| -rw-r--r-- | src/Hamming/Hamming.c | 174 | ||||
| -rw-r--r-- | src/Hamming/Hamming.h | 68 | ||||
| -rw-r--r-- | src/Hamming/HammingCalculateParityFast.c | 67 | ||||
| -rw-r--r-- | src/Hamming/HammingCalculateParitySmall.c | 99 | ||||
| -rw-r--r-- | src/Hamming/HammingCalculateParitySmallAndFast.c | 64 | ||||
| -rw-r--r-- | src/Hamming/HammingCalculateParityTextbook.c | 100 | ||||
| -rw-r--r-- | src/Hamming/LICENSE | 201 | ||||
| -rw-r--r-- | src/Hamming/README.md | 4 |
8 files changed, 777 insertions, 0 deletions
diff --git a/src/Hamming/Hamming.c b/src/Hamming/Hamming.c new file mode 100644 index 0000000..cb1fba3 --- /dev/null +++ b/src/Hamming/Hamming.c @@ -0,0 +1,174 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include <avr/pgmspace.h> + +#include "Hamming.h" + +/****************************/ +/* */ +/* Constants and structures */ +/* */ +/****************************/ + +#ifndef null +#define null ((void*) 0) +#endif + +// If transmitting/writing only, you don't need to include this file. +// If receiving/reading, then this provides the methods to correct bit errors. + +#define UNCORRECTABLE 0xFF +#define ERROR_IN_PARITY 0xFE +#define NO_ERROR 0x00 + + +/****************************/ +/* */ +/* Global variables */ +/* */ +/****************************/ + +// Private table. Faster and more compact than multiple if statements. +static const byte _hammingCorrect128Syndrome[16] PROGMEM = +{ + NO_ERROR, // 0 + ERROR_IN_PARITY, // 1 + ERROR_IN_PARITY, // 2 + 0x01, // 3 + ERROR_IN_PARITY, // 4 + 0x02, // 5 + 0x04, // 6 + 0x08, // 7 + ERROR_IN_PARITY, // 8 + 0x10, // 9 + 0x20, // 10 + 0x40, // 11 + 0x80, // 12 + UNCORRECTABLE, // 13 + UNCORRECTABLE, // 14 + UNCORRECTABLE, // 15 +}; + +/****************************/ +/* */ +/* Private methods */ +/* */ +/****************************/ + +// Give a pointer to a received byte, +// and given a nibble difference in parity (parity ^ calculated parity) +// this will correct the received byte value if possible. +// It returns the number of bits corrected: +// 0 means no errors +// 1 means one corrected error +// 3 means corrections not possible +static byte HammingCorrect128Syndrome(byte* value, byte syndrome) +{ + // Using only the lower nibble (& 0x0F), look up the bit + // to correct in a table + byte correction = pgm_read_byte(&(_hammingCorrect128Syndrome[syndrome & 0x0F])); + + if (correction != NO_ERROR) + { + if (correction == UNCORRECTABLE || value == null) + { + return 3; // Non-recoverable error + } + else + { + if ( correction != ERROR_IN_PARITY) + { + *value ^= correction; + } + + return 1; // 1-bit recoverable error; + } + } + + return 0; // No errors +} + + +/****************************/ +/* */ +/* Public methods */ +/* */ +/****************************/ + +// Given a pointer to a received byte and the received parity (as a lower nibble), +// this calculates what the parity should be and fixes the received value if needed. +// It returns the number of bits corrected: +// 0 means no errors +// 1 means one corrected error +// 3 means corrections not possible +byte HammingCorrect128(byte* value, nibble parity) +{ + byte syndrome; + + if (value == null) + { + return 3; // Non-recoverable error + } + + syndrome = HammingCalculateParity128(*value) ^ parity; + + if (syndrome != 0) + { + return HammingCorrect128Syndrome(value, syndrome); + } + + return 0; // No errors +} + + +// Given a pointer to a first value and a pointer to a second value and +// their combined given parity (lower nibble first parity, upper nibble second parity), +// this calculates what the parity should be and fixes the values if needed. +// It returns the number of bits corrected: +// 0 means no errors +// 1 means one corrected error +// 2 means two corrected errors +// 3 means corrections not possible +byte HammingCorrect2416(byte* first, byte* second, byte parity) +{ + byte syndrome; + + if (first == null || second == null) + { + return 3; // Non-recoverable error + } + + syndrome = HammingCalculateParity2416(*first, *second) ^ parity; + + if (syndrome != 0) + { + return HammingCorrect128Syndrome(first, syndrome) + HammingCorrect128Syndrome(second, syndrome >> 4); + } + + return 0; // No errors +} diff --git a/src/Hamming/Hamming.h b/src/Hamming/Hamming.h new file mode 100644 index 0000000..7778a59 --- /dev/null +++ b/src/Hamming/Hamming.h @@ -0,0 +1,68 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#ifndef _HAMMING_H +#define _HAMMING_H + +#ifndef _AVR_H +typedef unsigned char byte; +typedef unsigned char nibble; +#endif + +/**** These are needed to transmit and receive ****/ + +// Given a byte to transmit, this returns the parity as a nibble +nibble HammingCalculateParity128(byte value); + +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second); + + + +/**** These are needed only to receive ****/ + +// Given a pointer to a received byte and the received parity (as a lower nibble), +// this calculates what the parity should be and fixes the received value if needed. +// It returns the number of bits corrected: +// 0 means no errors +// 1 means one corrected error +// 3 means corrections not possible +byte HammingCorrect128(byte* value, nibble parity); + +// Given a pointer to a first value and a pointer to a second value and +// their combined given parity (lower nibble first parity, upper nibble second parity), +// this calculates what the parity should be and fixes the values if needed. +// It returns the number of bits corrected: +// 0 means no errors +// 1 means one corrected error +// 2 means two corrected errors +// 3 means corrections not possible +byte HammingCorrect2416(byte* first, byte* second, byte parity); + +#endif // _HAMMING_H diff --git a/src/Hamming/HammingCalculateParityFast.c b/src/Hamming/HammingCalculateParityFast.c new file mode 100644 index 0000000..6cc5df6 --- /dev/null +++ b/src/Hamming/HammingCalculateParityFast.c @@ -0,0 +1,67 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include <avr/pgmspace.h> + +#include "Hamming.h" + + +// This contains all of the precalculated parity values for a byte (8 bits). +// This is very fast, but takes up more program space than calculating on the fly. +static const byte _hammingCalculateParityFast128[256] PROGMEM = +{ + 0, 3, 5, 6, 6, 5, 3, 0, 7, 4, 2, 1, 1, 2, 4, 7, + 9, 10, 12, 15, 15, 12, 10, 9, 14, 13, 11, 8, 8, 11, 13, 14, + 10, 9, 15, 12, 12, 15, 9, 10, 13, 14, 8, 11, 11, 8, 14, 13, + 3, 0, 6, 5, 5, 6, 0, 3, 4, 7, 1, 2, 2, 1, 7, 4, + 11, 8, 14, 13, 13, 14, 8, 11, 12, 15, 9, 10, 10, 9, 15, 12, + 2, 1, 7, 4, 4, 7, 1, 2, 5, 6, 0, 3, 3, 0, 6, 5, + 1, 2, 4, 7, 7, 4, 2, 1, 6, 5, 3, 0, 0, 3, 5, 6, + 8, 11, 13, 14, 14, 13, 11, 8, 15, 12, 10, 9, 9, 10, 12, 15, + 12, 15, 9, 10, 10, 9, 15, 12, 11, 8, 14, 13, 13, 14, 8, 11, + 5, 6, 0, 3, 3, 0, 6, 5, 2, 1, 7, 4, 4, 7, 1, 2, + 6, 5, 3, 0, 0, 3, 5, 6, 1, 2, 4, 7, 7, 4, 2, 1, + 15, 12, 10, 9, 9, 10, 12, 15, 8, 11, 13, 14, 14, 13, 11, 8, + 7, 4, 2, 1, 1, 2, 4, 7, 0, 3, 5, 6, 6, 5, 3, 0, + 14, 13, 11, 8, 8, 11, 13, 14, 9, 10, 12, 15, 15, 12, 10, 9, + 13, 14, 8, 11, 11, 8, 14, 13, 10, 9, 15, 12, 12, 15, 9, 10, + 4, 7, 1, 2, 2, 1, 7, 4, 3, 0, 6, 5, 5, 6, 0, 3, +}; + +// Given a byte to transmit, this returns the parity as a nibble +nibble HammingCalculateParity128(byte value) +{ + return pgm_read_byte(&(_hammingCalculateParityFast128[value])); +} + +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second) +{ + return (pgm_read_byte(&(_hammingCalculateParityFast128[second]))<<4) | pgm_read_byte(&(_hammingCalculateParityFast128[first])); +} diff --git a/src/Hamming/HammingCalculateParitySmall.c b/src/Hamming/HammingCalculateParitySmall.c new file mode 100644 index 0000000..d446f8f --- /dev/null +++ b/src/Hamming/HammingCalculateParitySmall.c @@ -0,0 +1,99 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include "Hamming.h" + +/****************************/ +/* */ +/* Public methods */ +/* */ +/****************************/ + +// This is slower than using a table, but faster than +// using the textbook method. + +// Given a byte to transmit, this returns the parity as a nibble +nibble HammingCalculateParity128(byte value) +{ + // Exclusive OR is associative and commutative, so order of operations and values does not matter. + nibble parity; + + if ( ( value & 1 ) != 0 ) + { + parity = 0x3; + } + else + { + parity = 0x0; + } + + if ( ( value & 2 ) != 0 ) + { + parity ^= 0x5; + } + + if ( ( value & 4 ) != 0 ) + { + parity ^= 0x6; + } + + if ( ( value & 8 ) != 0 ) + { + parity ^= 0x7; + } + + if ( ( value & 16 ) != 0 ) + { + parity ^= 0x9; + } + + if ( ( value & 32 ) != 0 ) + { + parity ^= 0xA; + } + + if ( ( value & 64 ) != 0 ) + { + parity ^= 0xB; + } + + if ( ( value & 128 ) != 0 ) + { + parity ^= 0xC; + } + + return parity; +} + +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second) +{ + return (HammingCalculateParity128(second) << 4) | HammingCalculateParity128(first); +} + diff --git a/src/Hamming/HammingCalculateParitySmallAndFast.c b/src/Hamming/HammingCalculateParitySmallAndFast.c new file mode 100644 index 0000000..ad27bf8 --- /dev/null +++ b/src/Hamming/HammingCalculateParitySmallAndFast.c @@ -0,0 +1,64 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include <avr/pgmspace.h> + +#include "Hamming.h" + +/****************************/ +/* */ +/* Global variables */ +/* */ +/****************************/ + +// This contains all of the precalculated parity values for a nibble (4 bits). +static const byte _hammingCalculateParityLowNibble[] PROGMEM = +{ 0, 3, 5, 6, 6, 5, 3, 0, 7, 4, 2, 1, 1, 2, 4, 7 }; + +static const byte _hammingCalculateParityHighNibble[] PROGMEM = +{ 0, 9, 10, 3, 11, 2, 1, 8, 12, 5, 6, 15, 7, 14, 13, 4 }; + + +/****************************/ +/* */ +/* Public methods */ +/* */ +/****************************/ + +// Given a byte to transmit, this returns the parity as a nibble +nibble HammingCalculateParity128(byte value) +{ + return pgm_read_byte(&(_hammingCalculateParityLowNibble[value&0x0F])) ^ pgm_read_byte(&(_hammingCalculateParityHighNibble[value >> 4])); +} + +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second) +{ + return HammingCalculateParity128(second) << 4 | HammingCalculateParity128(first); +} diff --git a/src/Hamming/HammingCalculateParityTextbook.c b/src/Hamming/HammingCalculateParityTextbook.c new file mode 100644 index 0000000..08e5cca --- /dev/null +++ b/src/Hamming/HammingCalculateParityTextbook.c @@ -0,0 +1,100 @@ +/* +Hamming Error-Correcting Code (ECC) +Optimized for avr-gcc 4.8.1 in Atmel AVR Studio 6.2 +August 12, 2014 + +You should include Hamming.c, Hamming.h, and only one of the other Hamming files in your project. +The other Hamming files implement the same methods in different ways, that may be better or worse for your needs. + +This was created for LoFi in the TheHackadayPrize contest. +http://hackaday.io/project/1552-LoFi + +Copyright 2014 David Cook +RobotRoom.com + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + +http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include "Hamming.h" + +// This performs poorly on a processor that can't do multiple shifts in one instruction +#define BitToBool(byte, n) ((byte>>(n-1)) & 1) + +// This is a private method that calculates half the parity +// while shifting over any previously calculated parity for another byte. +// This was designed for processors that cannot shift more than one bit place at a time +nibble HammingCalculateParity2416Half(byte value, byte paritySoFar) +{ + // Calculate the most significant bit + paritySoFar |= BitToBool(value, 5) ^ BitToBool(value, 6) ^ BitToBool(value, 7) ^ BitToBool(value, 8); + // Shift it over + paritySoFar <<= 1; + + // Calculate the next most significant bit + paritySoFar |= BitToBool(value, 2) ^ BitToBool(value, 3) ^ BitToBool(value, 4) ^ BitToBool(value, 8); + // Shift it over, as well as the previously calculated bit + paritySoFar <<= 1; + + // Calculate the next most significant bit + paritySoFar |= BitToBool(value, 1) ^ BitToBool(value, 3) ^ BitToBool(value, 4) ^ BitToBool(value, 6) ^ BitToBool(value, 7); + // Shift it over, as well as the previously calculated bits + paritySoFar <<= 1; + + // Calculate the least significant bit + paritySoFar |= BitToBool(value, 1) ^ BitToBool(value, 2) ^ BitToBool(value, 4) ^ BitToBool(value, 5) ^ BitToBool(value, 7); + + return paritySoFar; +} + +// Given a byte to transmit, this returns the parity as a nibble +nibble HammingCalculateParity128(byte value) +{ + return HammingCalculateParity2416Half(value, 0); +} + +// If your processor can shift multiple bit places in a single instruction, then set this to 1. +// It will be twice as fast. +// If your processor cannot, then set this to 0, otherwise it will be slow and large. +#define CPU_HAS_MULTIPLE_SHIFT_INSTRUCTION 0 + +#if CPU_HAS_MULTIPLE_SHIFT_INSTRUCTION +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second) +{ + // This is the textbook way to calculate hamming parity. + return ((BitToBool(first, 1) ^ BitToBool(first, 2) ^ BitToBool(first, 4) ^ BitToBool(first, 5) ^ BitToBool(first, 7))) + + ((BitToBool(first, 1) ^ BitToBool(first, 3) ^ BitToBool(first, 4) ^ BitToBool(first, 6) ^ BitToBool(first, 7))<<1) + + ((BitToBool(first, 2) ^ BitToBool(first, 3) ^ BitToBool(first, 4) ^ BitToBool(first, 8))<<2) + + ((BitToBool(first, 5) ^ BitToBool(first, 6) ^ BitToBool(first, 7) ^ BitToBool(first, 8))<<3) + + + ((BitToBool(second, 1) ^ BitToBool(second, 2) ^ BitToBool(second, 4) ^ BitToBool(second, 5) ^ BitToBool(second, 7))<<4) + + ((BitToBool(second, 1) ^ BitToBool(second, 3) ^ BitToBool(second, 4) ^ BitToBool(second, 6) ^ BitToBool(second, 7))<<5) + + ((BitToBool(second, 2) ^ BitToBool(second, 3) ^ BitToBool(second, 4) ^ BitToBool(second, 8))<<6) + + ((BitToBool(second, 5) ^ BitToBool(second, 6) ^ BitToBool(second, 7) ^ BitToBool(second, 8))<<7); +} +#else +// Given two bytes to transmit, this returns the parity +// as a byte with the lower nibble being for the first byte, +// and the upper nibble being for the second byte. +byte HammingCalculateParity2416(byte first, byte second) +{ + // This makes two calls, one for each byte. + // It passes the result of the second byte into the calculation for the first + // such that the four shift instructions and the 'or' instruction are free. + return HammingCalculateParity2416Half(first, HammingCalculateParity2416Half(second, 0) << 1); +} +#endif + + diff --git a/src/Hamming/LICENSE b/src/Hamming/LICENSE new file mode 100644 index 0000000..5c304d1 --- /dev/null +++ b/src/Hamming/LICENSE @@ -0,0 +1,201 @@ +Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "{}" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright {yyyy} {name of copyright owner} + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/src/Hamming/README.md b/src/Hamming/README.md new file mode 100644 index 0000000..b6b8269 --- /dev/null +++ b/src/Hamming/README.md @@ -0,0 +1,4 @@ +Hamming +======= + +Hamming(12,8) and (24,16) error-correcting code (ECC) in avr-gcc |