libfgen  0.1.15
Library for optimization using a genetic algorithm or particle swarm optimization
gray.c
00001 /*
00002     gray.c -- Gray coding functions.
00003 
00004     fgen -- Library for optimization using a genetic algorithm or particle swarm optimization.
00005     Copyright 2012, Harm Hanemaaijer
00006 
00007     This file is part of fgen.
00008 
00009     fgen is free software: you can redistribute it and/or modify it
00010     under the terms of the GNU Lesser General Public License as published
00011     by the Free Software Foundation, either version 3 of the License, or
00012     (at your option) any later version.
00013 
00014     fgen is distributed in the hope that it will be useful, but WITHOUT
00015     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00016     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
00017     License for more details.
00018 
00019     You should have received a copy of the GNU Lesser General Public
00020     License along with fgen.  If not, see <http://www.gnu.org/licenses/>.
00021 
00022 */
00023 
00024 #include <stdint.h>
00025 #include "fgen.h"
00026 #include "parameters.h"
00027 
00028 /* Functions for Gray coding conversion. */
00029 /* Inspired by Usenet comp.ai.genetic FAQ. */
00030 
00031 
00032 static void ConvertBinaryToGray(const unsigned char *src, unsigned char *dest, int size_in_bytes) {
00033         int bitoffset;
00034         unsigned char *srcp, *destp;
00035         unsigned char savedbit;
00036         bitoffset = size_in_bytes * 8 - 1;
00037         srcp = (unsigned char *)src + bitoffset / 8;
00038         destp = (unsigned char *)src + bitoffset / 8;
00039         savedbit = *srcp & (1 << 7);
00040         *destp &= ~(1 << 7);
00041         *destp |= savedbit;
00042         savedbit >>= 7;
00043         bitoffset--;
00044         for (;;) {
00045                 int i;
00046                 if (bitoffset < 0)
00047                         break;
00048                 i = bitoffset & 7;
00049                 /*
00050                  * For second and following bytes, to derive the
00051                  * high order bit for the gray code, the
00052                  * saved last bit in the binary string from the
00053                  * previous byte is used.
00054                  */
00055                 while (i >= 0) {
00056                         unsigned char bit;
00057                         bit = *srcp & (1 << i);
00058                         *destp &= ~(1 << i);
00059                         *destp |= (savedbit << i) ^ bit;
00060                         savedbit = bit >> i;
00061                         i--;
00062                 }
00063                 bitoffset = (bitoffset & (~7)) - 1;
00064                 srcp--;
00065                 destp--;
00066         }
00067 }
00068 
00069 // General Gray-to-binary decoding function that is very slow.
00070 
00071 #define SetBit(str, offset, bit) \
00072         { \
00073                 unsigned char mask; \
00074                 unsigned char shift; \
00075                 shift = (offset) & 7; \
00076                 mask = 1 << shift; \
00077                 str[(offset) / 8] &= 0xFF - mask; \
00078                 str[(offset) / 8] |= (bit) << shift; \
00079         }
00080 
00081 #define GetBit(str, offset) \
00082         ((str[(offset) / 8] & (1 << ((offset) & 7))) >> ((offset) & 7))
00083 
00084 static void ConvertGrayToBinary(const unsigned char *src, unsigned char *dest, int size_in_bytes) {
00085         int i;
00086         i = size_in_bytes * 8 - 1;
00087         SetBit(dest, i, GetBit(src, i));
00088         i--;
00089         while (i >= 0) {
00090                 SetBit(dest, i, GetBit(dest, i + 1) ^ GetBit(src, i));
00091                 i--;
00092         }
00093 #if 0
00094         int bitoffset;
00095         unsigned char *srcp, *destp;
00096         unsigned char savedbit;
00097         bitoffset = size_in_bytes * 8 - 1;
00098         srcp = src + bitoffset / 8;
00099         destp = src + bitoffset / 8;
00100         savedbit = *srcp & (1 << 7);
00101         *destp &= ~(1 << 7);
00102         *destp |= savedbit;
00103         savedbit >>= 7;
00104         bitoffset--;
00105         for (;;) {
00106                 int i;
00107                 if (bitoffset < 0)
00108                         break;
00109                 i = bitoffset & 7;
00110                 /*
00111                  * For second and following bytes, to derive the
00112                  * high order bit for the binary code, the
00113                  * saved last bit in the binary string from the
00114                  * previous byte is used.
00115                  */
00116                 while (i >= 0) {
00117                         unsigned char bit;
00118                         bit = (*srcp & (1 << i)) ^ (savedbit << i);
00119                         *destp &= ~(1 << i);
00120                         *destp |= bit;
00121                         savedbit = bit >> i;
00122                         i--;
00123                 }
00124                 bitoffset = (bitoffset & (~7)) - 1;
00125                 srcp--;
00126                 destp--;
00127         }
00128 #endif
00129 }
00130 
00131 static unsigned int ConvertGrayToBinary8(unsigned int num) {
00132         unsigned int numBits = 8;
00133         unsigned int shift;
00134         for (shift = 1; shift < numBits; shift = 2 * shift)
00135                 num = num ^ (num >> shift);
00136         return num;
00137 }
00138 
00139 static unsigned int ConvertGrayToBinary16(unsigned int num) {
00140         unsigned int numBits = 16;
00141         unsigned int shift;
00142         for (shift = 1; shift < numBits; shift = 2 * shift)
00143                 num = num ^ (num >> shift);
00144         return num;
00145 }
00146 
00147 static unsigned int ConvertGrayToBinary32(unsigned int num) {
00148         unsigned int numBits = 8 * sizeof(num);
00149         unsigned int shift;
00150         for (shift = 1; shift < numBits; shift = 2 * shift)
00151                 num = num ^ (num >> shift);
00152         return num;
00153 }
00154 
00155 static uint64_t ConvertGrayToBinary64(uint64_t num) {
00156         unsigned int numBits = 8 * sizeof(num);
00157         unsigned int shift;
00158         for (shift = 1; shift < numBits; shift = 2 * shift)
00159                 num = num ^ (num >> shift);
00160         return num;
00161 }
00162 
00163 // Optimized decoding functions for common data element sizes.
00164 
00165 static void decode_from_gray_8(const FgenPopulation *pop, const unsigned char *src, unsigned char *dest) {
00166         int n = INDIVIDUAL_SIZE_IN_BYTES(pop);
00167         for (int i = 0; i < n; i++)
00168                 dest[i] = ConvertGrayToBinary8(src[i]);
00169 }
00170 
00171 static void decode_from_gray_16(const FgenPopulation *pop, const unsigned short *src, unsigned short *dest) {
00172         int n = INDIVIDUAL_SIZE_IN_BYTES(pop) / 2;
00173         for (int i = 0; i < n; i++)
00174                 dest[i] = ConvertGrayToBinary16(src[i]);
00175 }
00176 
00177 static void decode_from_gray_32(const FgenPopulation *pop, const unsigned int *src, unsigned int *dest) {
00178         int n = INDIVIDUAL_SIZE_IN_BYTES(pop) / 4;
00179         for (int i = 0; i < n; i++)
00180                 dest[i] = ConvertGrayToBinary32(src[i]);
00181 }
00182 
00183 static void decode_from_gray_64(const FgenPopulation *pop, const uint64_t *src, uint64_t *dest) {
00184         int n = INDIVIDUAL_SIZE_IN_BYTES(pop) / 8;
00185         for (int i = 0; i < n; i++)
00186                 dest[i] = ConvertGrayToBinary64(src[i]);
00187 }
00188 
00194 void fgen_decode_from_gray(const FgenPopulation *pop, const unsigned char *src_bitstring,
00195 unsigned char *dest_bitstring) {
00196         if (pop->data_element_size == 1 || pop->data_element_size == pop->individual_size_in_bits)
00197                 ConvertGrayToBinary(src_bitstring, dest_bitstring, INDIVIDUAL_SIZE_IN_BYTES(pop));
00198         else {
00199                 switch (pop->data_element_size) {
00200                 case 8 :
00201                         decode_from_gray_8(pop, src_bitstring, dest_bitstring);
00202                         return;
00203                 case 16 :
00204                         decode_from_gray_16(pop, (const unsigned short *)src_bitstring, (unsigned short *)dest_bitstring);
00205                         return;
00206                 case 32 :
00207                         decode_from_gray_32(pop, (const unsigned int *)src_bitstring, (unsigned int *)dest_bitstring);
00208                         return;
00209                 case 64 :
00210                         decode_from_gray_64(pop, (const uint64_t *)src_bitstring, (uint64_t *)dest_bitstring);
00211                         return;
00212                 default :
00213                         /* For each data element */
00214                         for (int i = 0; i < INDIVIDUAL_SIZE_IN_BYTES(pop) * 8 / pop->data_element_size; i++)
00215                                 ConvertGrayToBinary(src_bitstring + i * pop->data_element_size / 8, dest_bitstring +
00216                                         i * pop->data_element_size / 8, pop->data_element_size / 8);
00217                         break;
00218                 }
00219         }
00220 }
00221 
00227 void fgen_encode_to_gray(const FgenPopulation *pop, const unsigned char *src_bitstring,
00228 unsigned char *dest_bitstring) {
00229         if (pop->data_element_size == 1 || pop->data_element_size == pop->individual_size_in_bits)
00230                 ConvertBinaryToGray(src_bitstring, dest_bitstring, INDIVIDUAL_SIZE_IN_BYTES(pop));
00231         else {
00232                 int i;
00233                 /* For each data element */
00234                 for (i = 0; i < INDIVIDUAL_SIZE_IN_BYTES(pop) * 8 / pop->data_element_size; i++)
00235                         ConvertBinaryToGray(src_bitstring + i * pop->data_element_size / 8, dest_bitstring +
00236                                 i * pop->data_element_size / 8, pop->data_element_size / 8);
00237         }
00238 }
00239 
 All Data Structures Functions Variables