Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #76169

Re: Parsing a rotated stream of 64 bits

Show all headers | View raw

Il 15/11/2015 21:02, Tim Rentsch ha scritto:
> pozz <pozzugno@gmail.com> writes:
>
>> Il 10/11/2015 23:00, Tim Rentsch ha scritto:
>>> pozz <pozzugno@gmail.com> writes:
>>>
>>>> Il 30/10/2015 17:18, Tim Rentsch ha scritto:
>>>>
>>>>> Seems like a lot of code and a lot of computational effort for
>>>>> the task.  Here is a shorter and probably faster method that I
>>>>> think conforms to your interface.
>>>>
>>>> I measured both implementation on AVR ATtiny4313 MCU running at 8MHz.
>>>>
>>>> My implementation takes about 350us.  Your implementation more than 700us.
>>>>
>>>> I didn't study your implementation too much, I only put it as is in my
>>>> project.
>>>
>>> This doesn't tell me very much.  Presumably your code is tuned
>>> both for the architecture and for the compiler used to compile
>>> it.  My code is tuned for neither.  I suspect a lot depends on
>>> that but I don't know what, since I don't have access to either.
>>> I don't expect you to put in extra effort just to tailor my code
>>> to that environment, but it would be nice to see if we could do
>>> an apples-and-apples comparison.  Could I ask what compiler
>>> you're using and what system it runs on?
>>
>> As David supposed, I'm using avr-gcc for generate code for ATtiny4313
>> MCU (8-bit AVR core).
>
> Here is a followup now that I've had a chance to use the avr-gcc
> compiler.
>
> There were two obvious problems with the code I posted earlier.
> One is that it uses 'unsigned' rather than 'unsigned char' for
> its local variables.  The other is that it uses variable length
> shifts, which as suggested are done using loops (and not a single
> variable length shfit instruction).  Also there are some common
> subexpressions that I thought the compiler would be smart enough
> to keep around, but apparently it wasn't.  All of these can be
> worked around:  I reworked the code so all shifts are of constant
> values, and common subexpression values were kept in variables
> explicitly (which also eliminated some other variables in the
> process).  No variable needs more than eight bits, so changing to
> unsigned char was trivial.  I think a hybrid strategy is also
> possible but I haven't tried coding it - keeping the same general
> structure for the main routine, but doing some easy cleanup
> around variable sizes and common subexpression values.  Also the
> function to find where the preamble ends is easy to rework so it
> uses 1-bit shifts rather than the variable length shifts it uses
> now.  The reworked code is a single function and just a little
> longer (five or ten lines more) than your two functions together
> (counting only the function bodies in both cases).
>
> If I were responsible for coding this I would want to ask about
> what the performance requirements are.  Unless it really is a
> problem for decoder to run at the (slower) speed you mentioned, I
> think the shorter code is better, because it's smaller, more
> modular, and (IMO) easier to understand.  If on the other hand
> performance is crucial, I expect my reworked code is faster than
> the code you posted, because some of the bookkeeping has been
> eliminated;  but, since I don't have an environment in which to
> measure how fast different functions run, that is only an
> educated guess based on looking at the generated code in the
> several cases.

The speed of my code is sufficient, but if it's possible to improve...
Please, share your reworked code.


> I do see now, at least to some extent, the problem you're up
> against - it is hard to write code for this processor that is
> both fast and easy to understand.  Having said that, I still
> think we could do better than the one-bit-at-a-time method that
> was posted earlier.
>
> Incidentally, I believe your code has a bug in that sometimes it
> gets confused about where the preamble starts.  This happens in
> some cases when the preamble straddles the buffer edge and the
> first four-bit field has a leading 1 bit.

Yes, you are right. Thank you for the suggestion. I have to search for a 
zero bit, before searching for the 9 1-bits.
Considering the EM4100 code structure, I *have to* see a 0-bit in the 
first 14 bits, otherwise the stream has an error for sure.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-10-27 23:54 +0100
  Re: Parsing a rotated stream of 64 bits Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-10-27 17:37 -0700
  Re: Parsing a rotated stream of 64 bits Bartc <bc@freeuk.com> - 2015-10-28 01:27 +0000
  Re: Parsing a rotated stream of 64 bits Nobody <nobody@nowhere.invalid> - 2015-10-28 05:13 +0000
  Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-28 09:17 +0100
    Re: Parsing a rotated stream of 64 bits supercat@casperkitty.com - 2015-10-28 06:22 -0700
      Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-28 16:07 +0100
        Re: Parsing a rotated stream of 64 bits supercat@casperkitty.com - 2015-10-28 08:41 -0700
          Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-28 23:29 +0100
            Re: Parsing a rotated stream of 64 bits supercat@casperkitty.com - 2015-10-28 17:50 -0700
              Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-29 13:56 +0100
          Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-10-29 09:48 +0100
    Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-10-29 09:34 +0100
      Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-29 13:57 +0100
  Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-10-28 09:21 +0100
  Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-28 23:44 -0700
    Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-10-29 09:28 +0100
      Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-30 09:18 -0700
        Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-11-09 09:27 +0100
          Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-10 14:00 -0800
            Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-11-11 10:48 +0100
              Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-13 05:56 -0800
                Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-11-13 16:32 +0100
                Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-14 17:57 -0800
                Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-11-15 23:43 +0100
                Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-17 08:42 -0800
            Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-11-13 14:58 +0100
              Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-15 12:02 -0800
                Re: Parsing a rotated stream of 64 bits pozz <pozzugno@gmail.com> - 2015-11-16 10:16 +0100
                Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-17 10:49 -0800
                Re: Parsing a rotated stream of 64 bits David Brown <david.brown@hesbynett.no> - 2015-11-17 23:34 +0100
                Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 16:04 -0800
    Re: Parsing a rotated stream of 64 bits Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-10-29 03:56 -0700
      Re: Parsing a rotated stream of 64 bits Tim Rentsch <txr@alumni.caltech.edu> - 2015-10-30 08:42 -0700
  Parsing a rotated stream of 64 bits asetofsymbols@gmail.com - 2015-11-16 03:03 -0800

csiph-web