Extended Hamming encode/decode
in [Embedded]
|
Prev: Announcement: New version of UML state machine code generator available
Next: CFP with Extended Deadline of Mar. 21, 2010: The 2010 International Conference on Computer Design (CDES'10), USA, July 2010
From: Jon Kirwan on 7 Mar 2010 18:12 On Sun, 07 Mar 2010 22:08:03 +0100, David Brown <david.brown(a)hesbynett.removethisbit.no> wrote: >Jon Kirwan wrote: >> On Sun, 07 Mar 2010 13:16:44 +0100, David Brown >> <david(a)westcontrol.removethisbit.com> wrote: >> >> <snip> >>> Why did you pick the LGPL? It basically means that people here can use >>> your code in test code, but can't (legally) use it in any "production" code. >> >> Partly, it was exactly because of your reaction. We've >> recently had a modest discussion about licensing and I have >> frankly found my reading of specific licenses to have muddled >> by understanding more than clarified it. So much to take in >> and it still hasn't gelled in my mind, yet. >> >> Partly, I think, because I'm not yet even sure what I want. > >Fair enough. Releasing the code now under the LGPL does not limit you >from releasing it under other licenses later. Agreed. I hate this stuff. It should be easier than it has become. I don't like not understanding the legal ramifications, but I don't. I think I'll re-release it when I figure out how. >> I'm very much open to ANY thoughts here. > >I'd go for a FreeRTOS-style modified GPL saying that the original >"library", and any changes made to it, must be released under the same >license, while other code linked to the "library" that only uses the >library's public interface is not bound by the license. eCOS has a >similar license: > ><http://ecos.sourceware.org/license-overview.html> Thanks, I'll look it over (and hope I understand it better than I did the LGPL.) >Alternatively, given that this is a fairly small amount of code and >there is no realistic chance that you will ever sue someone for stealing >it or abusing whatever license you pick, you could just put a notice >saying "Please retain the above copyright notice, provide a copy of this >file to anyone who asks, and publish any modifications and enhancements >to this code in a public forum such as comp.arch.embedded". Honest >users will respect your wishes, dishonest ones will ignore whatever >license you use. Yeah. The old way of doing things. >>> You should drop the "auto" keyword. It has been unnecessary in C for >>> decades, conflicts with newer C++ standards, and if there are in fact >>> any compilers that pay attention to it, it will generate worse code >>> (since "auto" is then a hint to the compiler to put the variable on the >>> stack, hindering the optimiser). >> >> I also use LET when writing BASIC code. It's an idiom of >> mine, I suppose. But it helps _me_ by placing a written word >> that explicitly calls my attention to its unique nature in >> functions and it harms nothing at all. > >Generally, I'm all for "explicit" rather than "implicit". I consider >the "implicit int" in C to be one of the language's many failings. But >the keyword "auto" is so archaic that it's only purpose is to confuse >programmers with less than twenty years of experience. And it conflicts >directly with modern C++ - that's an indication of how rarely it is used >in any C code you'd find these days. Unnecessary and gratuitous >conflicts with C++ is, I would say, harmful. (I would say the opposite >too - for example, in the little C++ I write, a function taking no >parameters is void foo(void), which is valid in both languages.) I'll hope to hear from others on this topic, rather than just jumping forward and either accepting or rejecting this argument. I have my habits and, for now, I can afford to keep them. But you've put me on notice. >> I use a lot of languages, not just c, and I have used so many >> more. Everything from RPG II and COBOL and Algol and various >> assembly languages, starting around 1970 or so through BASIC >> a few years later and c in '78 (I remember, because it was >> with Unix v6 kernel code) and c++ in about '87, or so. > >Yet you have clearly written this code for the benefit of others, not >yourself - thus you have to balance your idiosyncrasies with standard >practice. I too program in many languages, and have particular ways of >writing my code - I would change my style for code published for general >use. If I agreed. But that jury is still out. For now, I'll leave it as is. Others will, of course, be free to do as they please. But you aren't talking about "this code" but about my future writing style, David. And that is a lot bigger issue than just this case and involves a profound change of earlier habits, as well. It warrants more thought and some research and probably some listening to others. >> Because of the breadth of languages I still continue to use, >> it also saves me from just that very tiny extra moment of >> thought about c, in particular. Without the 'auto' keyword, >> the same line, outside a function, works but has a storage >> type, life span, and visibility that is marked different and >> I don't like having to pause even a moment. The 'auto' >> keyword takes a fraction of a moment to type and it pays, >> time and time again later on for me. >> >> I've been known to use LET in BASIC code, too. >> >> I don't know if this is a habit I want to shed. However, I'd >> like to know more about why you wrote "conflicts with newer >> c++ standards." Can you provide a standards document >> reference I can go to on this subject? Or is this simply a >> "new standard" that is developing within the gcc community >> that I need to learn about? > ><http://en.wikipedia.org/wiki/C%2B%2B0x#Type_inference> ><http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1984.pdf> ><http://gcc.gnu.org/projects/cxx0x.html> > >Basically, in C++0x (a standard started over ten years ago, and still >not fully implemented - who said the computer world moved quickly?), you >can use "auto" as the a type in a variable declaration when the compiler >can infer the true type from the initialiser. Thus "auto x = 1;" makes >x an int (the type of "1"). It's main use is when using or defining >templates, where variable type declarations can get seriously messy - >the programmer knows what they mean, but getting the ugly details right >is hard work. Ah. Back to templates and c++. As I mentioned already, had I been writing in c++ I would have used templates. And your arguments would carry more weight, I think. Regardless of your writing here that I should consider c++ when writing c, in this case it is so much better to use templates if using c++ that I just don't imagine the code I'm writing here will ever find much purchase in c++. It's just so much better as templated code that most anyone would rush to that point and not use what I wrote, except as at most some guide or test comparison. >> Also, a final point. It used to have no cost and have no >> change in the compiler behavior -- certainly that remains >> true with c, which is the language I chose here. Had I been >> using c++ for this code, which is a different language as I >> am continually reminded of, I would have written it as a >> template class allowing instancing, as needed. Do you argue >> that when I write c, not c++, that I need to be aware of your >> comments regarding this "new standard?" > >Yes, I argue that. C and C++ are different languages - but they are >close enough, and have enough in common, that it is silly to write code >that does not work as expected in the other language unless you have >good reason. There are many incompatibilities between C and C++ in >theory - but there are none where the C code would be worsened by making >it work equally well with C++. See above comments. >Treat C++ as though it were yet another C standard. You wouldn't write >code that worked with C90 but failed with C99 (though you may write code >that worked with C99 and not with C90, taking advantage of the newer >functionality and ignoring the obsolete standard). Don't write code >that works with C and not C++ without good reason - and as far as I >know, there are no good reasons. I'm still on C90 for almost everything I do. And I can absolutely assure you, right here and now, that I will _not_ write code that requires C99 compliance even when writing c. Not yet, anyway. Perhaps when C99 becomes more widely supported. Writing for C90 means it will work in C99. Writing for C99 does NOT mean it will work with a C90 compiler. >>> You have a "hamm_def.h" include file to define your own non-standard >>> sized integer types that are not actually portable or accurate (at the >>> very least, use "short int" for 16-bit - it's not universal, but it is >>> more portable than plain "int"). Since you are clearly aiming for >>> portable code, you would be much better using "#include <stdint.h>" and >>> using modern sized integer types. It is perfectly reasonable to expect >>> people to have <stdint.h> these days - anyone who needs to use your code >>> with ancient tools will simply have to put in their own typedefs. >> >> Thanks for that. I just checked a couple of c compiler >> implementations I have here and am still supporting, >> actively, for customers. There is no stdint.h file in their >> include directories. Doesn't exist. For example, it's not >> present in Lattice c or in Microsoft's VC 1.52c (which is the >> actual target for this code.) And I still support systems >> written in both of these compiler tools, that are used in >> modern FABs today for IC manufacturing. If you can believe >> it. > >Sometimes in this industry, you have to deal with ancient systems or >ancient tools - I know that well. But you have to draw a line and say >that the code you write today is for the systems available today, and >for use with today's software and today's tools. Well, you have my answer to that. Someone else's job, if they want it. C90 remains the "portable" standard for me for embedded use. Not C99. Not c++. >You take advantage of >the modern tools and their benefits. If it turns out that you need to >retrofit your new code to work with an old system, /that/ is the time to >go out of your way to make it work there. For example, I use // >comments because they are neater and clearer than /* */ comments (for >short comments), even though I have a few compilers that don't support >them. But I won't limit myself just for the sake of a couple of >projects I haven't touched for years. Well, we will simply have to leave this unresolved between us, then. I can follow your argument, but I don't embrace it. >And of course in this case, writing your own "stdint.h" for your old C90 >compiler is not exactly difficult. hehe. It's not. But... that means I then need to provide that and they need to stuff it into the right directory (if I use <> instead of "".) More work. However, this discussion has convinced me to remove hamm_def.h completely. It's really more of an annoyance than a help and I think you've convinced me of that much. New code is reposted, already. >Note that this is different from using new features or being >incompatible just for the sake of it - there has to be some benefit in it. .... Oh, well. >> It is a C99 standard, not C90. I honestly wish that I could >> rely upon C99 (despite some sour comments I've read from at >> least one compiler author, who I trust to know what he speaks >> of, that C99 is a terrible standard... an opinion I'm not >> well enough informed about to argue either way), but that > >C is a terrible language, and C99 is a terrible standard - but they are >the best we've got in this industry. No, C90 is the best. C99 isn't always there. >> simply isn't even the modern world of compiler tools for >> embedded use I'm exposed to (and I'm not suggesting that VC++ >> 1.52C is modern, so don't mistake me here.) Only a very few >> of the compiler tools I have access to attempt much of C99, >> though I've no doubt that stdint.h is an easy one for them. > >Most modern compilers (less than 5 years old, say) implement a fair >amount of C99. Few (if any) implement it all. But the missing features >are seldom relevant - that's why the compiler writers haven't bothered >to implement them. See for example: > ><http://gcc.gnu.org/c99status.html> > >There is nothing "missing" that is worth bothering about for most >programs. The compiler industry is slow, but after ten years anything >that is worth implementing, and that programmers want to use, has been >implemented. I use gcc only rarely in my applications. >> This leaves me arguing that I would prefer to rely upon a >> base I _can_ fairly require, which is C90. > >You can rely on modern compilers implementing the important parts of C99 >in the same way as you can rely on any compiler to generate correct code >- i.e., you are normally safe but sometimes you'll get caught out. No, C90. >> I'm still open to an argument here or other ideas. >> >>> Having first defined these size-specific types, you then ignore them in >>> the code and use that most hideous of illogical expression, the >>> "unsigned char". >> >> No, the specified size is on purpose, Dave (setting aside for >> a moment what you will address in a moment regarding my use >> of unsigned.) >> >> In this case, the check values will NEVER exceed that size. >> Because of that fact, I can insist on it. There is no need >> for the user of this code to worry about that detail, because >> I have. Check values, plus parity, of 8 bits will cover 128 >> bit words. For those interested in exceeding that with my >> code, I suppose they can modify the code to deal with it. (I >> might have created a separate typedef, I suppose.) > >I'm not arguing against your use of __HAMM_VALUE_T for size-specific >types - far from it (though I argue against your use of "__", and I >forgot to complain about the use of all-caps being ugly to read). hehe. What would you consider to be pretty? >I'm arguing against using "unsigned char" when what you really mean is >"unsigned 8-bit integer", generally written "uint8_t". Hmm. okay. I changed that. More ugliness, but what the heck. __HAMM_CHECK_T is used throughout, now. ;) >> Do you have a good way I might be able to use sizeof() in a >> #if? I seem to recall that doesn't work. > >No, you can't use sizeof in an #if. But I can't see why you might want >to do that here - perhaps we are misunderstanding each other? Oh, something like this: #if sizeof( __HAMM_VALUE_T ) == 2 might be useful. There is code that is either needed, or not needed, depending on the word size. It would be nice to modify code depending upon the number of check bits required and the size of the data word. That's all. >>> Until someone can draw me two letter "a"s and explain >>> to me why one of these is "signed" and the other "unsigned", I will only >>> use "char" for holding a character. >> >> Well, then we have a serious problem, Dave. There is quite a >> difference between c's handling of signed and unsigned in >> terms of conversions and in this particular case, it becomes >> important. A shift operation is only one such reason. >> >> If you are interested in exploring what happens, go ahead and >> change the unsigned chars to just char and modify the 1U to a >> 1, instead, in hamm_xx.c and recompile and check the results. >> > >I know all about C's handling of "signed char" and "unsigned char" - >that's not the issue. > >But a "char" is a "character", i.e., a letter or character in a string. > Regardless of what K&R thought, it makes no logical sense to talk >about a "signed" letter - just as it makes no sense to talk about an >upper-case number. "signed char" is a meaningless concept in itself - >and using any sort of "char" for numbers is dangerous because people >think they can use plain "char", and then get trouble with >signed/unsigned issues. > >It is true that the original C had no better standard for 8-bit data, >but C99 does have better types - they are called "uint8_t" and "int8_t". > And if you have to use a compiler without <stdint.h>, then you define >these types yourself. ><snip> :) I'm still back on C90. I've enjoyed this and you've made me think a little and change a few things in the process. Plus, I'm still hoping to learn something about various licenses, too. So all to the good, I think. I'm very glad you took me to task. It's improved things, already. (I also found a bug caused by some last second changes I'd made for silly efficiency reasons and I owe you for that.) Jon
From: Vladimir Vassilevsky on 7 Mar 2010 19:22 Jon Kirwan wrote: > > Thanks, Vladimir. That helps a lot. This isn't Hamming, But that *is* Hamming. VLV
From: Jon Kirwan on 7 Mar 2010 19:29 On Sun, 07 Mar 2010 18:22:46 -0600, Vladimir Vassilevsky <nospam(a)nowhere.com> wrote: >Jon Kirwan wrote: >> >> Thanks, Vladimir. That helps a lot. This isn't Hamming, > >But that *is* Hamming. Okay. Of course. I guess I meant as separate from reed solomon and gegenbauer. Which is why I mentioned the dates you removed from my post in replying. Jon
From: David Brown on 7 Mar 2010 19:45 Jon Kirwan wrote: > On Sun, 07 Mar 2010 20:23:26 +0100, David Brown > <david.brown(a)hesbynett.removethisbit.no> wrote: > >> steve_schefter(a)hotmail.com wrote: >>> Hi David. >>> >>>> Why did you pick the LGPL? It basically means that people here can use >>>> your code in test code, but can't (legally) use it in any "production" code. >>> This isn't my impression of LGPL. Can I ask what leads you to that >>> conclusion? >>> >>> Steve >> To use LGPL'ed code with your own code, anyone receiving your code must >> have access to the LGPL'ed code, be able to change and recompile that >> code, then link it along with the rest of the binary and run that >> software instead. > > In this case, though, the files stand alone. So all the code > is there and anyone is able to change and recompile it. > > I'm still confused, I suppose. > >> For non-embedded systems (or "big" embedded systems), >> that typically means the LGPL'ed code is part of a dynamic library. > > But in this case, it's a stand alone set of files that can be > included into the project as another module. It is just what > it is, and no more than that. > > I'm still confused about what this means to small or large > systems or why it would make any difference. > >> To >> use LGPL code in a (typically statically linked) embedded system means >> that the end user will need access to your source code, or at least >> compiled and linkable object files. > > But since I'm providing all of the source, they have all > that. Right? > >> Since that is impractical or >> impossible for most embedded systems, the rough conclusion is that pure >> LGPL code is very seldom suitable for embedded systems. > > I wish I followed from your premises to your conclusion here. > This is where I'm stuck. I think I can almost understand > your earlier points -- maybe -- but if I do, your conclusion > doesn't follow from them. So I must not understand them. > Which means I still can't reach the conclusion. I feel dumb > about this, but there it is. > >> Of course, in some cases that is exactly what the code supplier is >> intending - the end user is able to use the code for evaluation and >> testing, and in non-commercial systems (and also for internal use), but >> for a commercial system they would get a separate license from the code >> supplier. That's a valid way of licensing code to developers. But I >> don't think that was Jon's intention here. > > No, it's not. You are right on that point. > >> This has been covered endlessly in previous threads in this newsgroup - >> please let's not have another one unless someone has new points that >> were not covered recently. > > yeah. And I still can't say I am better informed than > beforehand. Probably just me. But I can use some hand > holding from those who imagine they follow all this well. > > Jon At some point, you're going to get an "ah-ha" moment and wonder why you couldn't see it earlier... The problem is not with your code - it is with other people's. Suppose I make a little wireless sensor that uses your hamming code as part of the software. I've got other modules for reading the sensor, making the obligatory LED blink, and so on. Since the hamming code is under the LGPL, I give the end user a copy of your hamming code (or a written offer, valid for three years, etc., etc., according to the LGPL). The end user finds a bug in the hamming code, and corrects it. He wants to use this new version in the sensor instead of the old one. The LGPL gives him the right to do this - I therefore have to pass him the source code, or at least linkable object files, for the rest of my code. Note only does he have the right to such code, along with whatever information is needed to be able to compile, link, download and run the new binary, but he is free to pass everything along to anyone else. /Now/ do you see why embedded developers can't (in general) use LGPL'ed code, unless there is an explicit exception such as is used in eCOS and FreeRTOS licenses? mvh., David
From: Vladimir Vassilevsky on 7 Mar 2010 20:02
Jon Kirwan wrote: > On Sun, 07 Mar 2010 18:22:46 -0600, Vladimir Vassilevsky > <nospam(a)nowhere.com> wrote: > > >>Jon Kirwan wrote: >> >>>Thanks, Vladimir. That helps a lot. This isn't Hamming, >> >>But that *is* Hamming. > > Okay. Of course. I guess I meant as separate from reed > solomon and gegenbauer. Huh? Reed-Solomons are nonbinary; as for Gegenbauer, he is from different bookshelf :))) > Which is why I mentioned the dates > you removed from my post in replying. VLV |