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

Groups > comp.lang.c > #74023 > unrolled thread

Parsing a rotated stream of 64 bits

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#75724

On 10/11/15 23:00, Tim Rentsch wrote:
> 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?
> 

If you are unfamiliar with the AVR, it is an 8-bit RISC cpu with 32
registers.  There are a few compilers for it, but by far the most
commonly used is gcc (it is the only 8-bit target in mainline gcc).
Register to register operations are fast, but only for 8-bit - when
using 16 bits, you need twice the instructions (at least).  It has a
three pointer registers, with slightly varying address modes - if code
needs more than those it quickly gets very slow.  And division/mod is
very slow, except for powers of two (and even then you only get
single-bit shift/rotate per cycle).  I don't think the chip in question,
the ATtiny4313, has a hardware multiplier - so multiplication is also slow.

With that in mind, I don't see anything in the code you wrote that would
be particularly slow on the AVR, except that you should use "uint8_t"
rather than "unsigned" wherever possible.  It is possible that in your
"em4100_decode" function, it would be worth tracking "k/8" and "k%8" as
separate variables, but gcc's optimiser may handle that.  Variable
length shifts are slow on the AVR - it means either a loop or a library
call, so these should be avoided if possible.  But if speed is critical,
it might be possible to get gcc to generate significantly faster code
with careful choices of optimisation flags (such as to force loop
unrolling) as well as using 8-bit types.

[toc] | [prev] | [next] | [standalone]

#75950

David Brown <david.brown@hesbynett.no> writes:

> On 10/11/15 23:00, Tim Rentsch wrote:
>> 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?
>
> If you are unfamiliar with the AVR, it is an 8-bit RISC cpu with
> 32 registers.  There are a few compilers for it, but by far the
> most commonly used is gcc (it is the only 8-bit target in mainline
> gcc).  Register to register operations are fast, but only for
> 8-bit - when using 16 bits, you need twice the instructions (at
> least).  It has a three pointer registers, with slightly varying
> address modes - if code needs more than those it quickly gets very
> slow.  And division/mod is very slow, except for powers of two
> (and even then you only get single-bit shift/rotate per cycle).  I
> don't think the chip in question, the ATtiny4313, has a hardware
> multiplier - so multiplication is also slow.  [snip other possible
> pitfalls]

Thank you, this is quite helpful.  Probably the culprit here
is variable length shifts, which my code has a lot of.  But
I should be able to work around that.

Do you by chance know what options to give gcc so that it targets
this architecture?  What I'm looking for in particular is having
gcc show generated assembly so I can look at that.

Thank you again for the help!

[toc] | [prev] | [next] | [standalone]

#75954

On 13/11/15 14:56, Tim Rentsch wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 10/11/15 23:00, Tim Rentsch wrote:
>>> 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?
>>
>> If you are unfamiliar with the AVR, it is an 8-bit RISC cpu with
>> 32 registers.  There are a few compilers for it, but by far the
>> most commonly used is gcc (it is the only 8-bit target in mainline
>> gcc).  Register to register operations are fast, but only for
>> 8-bit - when using 16 bits, you need twice the instructions (at
>> least).  It has a three pointer registers, with slightly varying
>> address modes - if code needs more than those it quickly gets very
>> slow.  And division/mod is very slow, except for powers of two
>> (and even then you only get single-bit shift/rotate per cycle).  I
>> don't think the chip in question, the ATtiny4313, has a hardware
>> multiplier - so multiplication is also slow.  [snip other possible
>> pitfalls]
> 
> Thank you, this is quite helpful.  Probably the culprit here
> is variable length shifts, which my code has a lot of.  But
> I should be able to work around that.
> 
> Do you by chance know what options to give gcc so that it targets
> this architecture?  What I'm looking for in particular is having
> gcc show generated assembly so I can look at that.
> 
> Thank you again for the help!
> 

(I am not sure if you know all this and I've misunderstood your question
slightly, or if it is new to you because you have little or no
experience of cross-compilation.  So what I write here will either be
helpful and interesting, or sound obvious and patronising.  Hopefully it
will be the former!)

Just to get you started with the AVR, beyond what I wrote earler:

<https://en.wikipedia.org/wiki/Atmel_AVR>

It's an 8-bit microcontroller architecture, made by Atmel.  The main
product page is here:

<http://www.atmel.com/products/microcontrollers/avr/default.aspx>

(There is also an "AVR32" made by Atmel - it shares little with the AVR
except the name.  Although the main compiler for the AVR32 is also gcc,
it is outside the main gcc tree and maintained entirely by Atmel.
Basically, the AVR32 is a dead-end architecture, since Atmel also make
ARM microcontrollers - a shame really, since it was quite a nice cpu.
So here we are only discussing the 8-bit AVR devices.)

Pick a device if you want to see the datasheet and read about the cpu:

<http://www.atmel.com/devices/ATMEGA3250.aspx?tab=documents>


Regarding the compiler, the gcc source supports the AVR (and a couple of
dozen other architectures), but any given binary build is for a specific
host-target combination.  So the gcc that you no doubt have installed on
your system from before cannot target the AVR.  You can always download
the gcc source and build it yourself, but probably you will do better to
simply download the ready-build packages from Atmel:

<http://www.atmel.com/tools/ATMELAVRTOOLCHAINFORLINUX.aspx>

That gets you the compiler, binutils (assembler, linker, etc.), the
library (avrlibc), device headers, etc.  The avrlibc project home page
is another source of useful information:

<http://www.nongnu.org/avr-libc/>

Once you have the tools installed, a typical command line to compile a C
file and look at the generated assembly would be:

avr-gcc -mmcu=atmega3250 -c -Os -std=gnu11 -Wall -Wa,-adchls=test.lst test.c

-mmcu=atmega3250 specifies the device (the format here may be different
in newer avrgcc builds - it's a while since I used a new version, since
I make a point of never changing toolchains in a project and I haven't
had any recent AVR projects).

-c = compile (no linking)
-Os = optimise for size, a common choice on microcontrollers
-std=gnu11 = C11 standards with gcc extensions
-Wall = Lots of warnings
-Wa,-adchls=test.lst = ask for an assembly listing file


We no longer make much use of AVR devices in new products, but we've
used them a lot in the past.  The architecture is very interesting as it
is the only 8-bit cpu supported by gcc - it is one of very few 8-bit
RISC architectures.  It can be interesting to see what sort of code gets
generated for one of the smallest cpus that can be called "C friendly" -
it will challenge some of your assumptions about what is "cheap" in C.

[toc] | [prev] | [next] | [standalone]

#76068

David Brown <david.brown@hesbynett.no> writes:

> On 13/11/15 14:56, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 10/11/15 23:00, Tim Rentsch wrote:
>>>> 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?
>>>
>>> If you are unfamiliar with the AVR, it is an 8-bit RISC cpu with
>>> 32 registers.  There are a few compilers for it, but by far the
>>> most commonly used is gcc (it is the only 8-bit target in mainline
>>> gcc).  Register to register operations are fast, but only for
>>> 8-bit - when using 16 bits, you need twice the instructions (at
>>> least).  It has a three pointer registers, with slightly varying
>>> address modes - if code needs more than those it quickly gets very
>>> slow.  And division/mod is very slow, except for powers of two
>>> (and even then you only get single-bit shift/rotate per cycle).  I
>>> don't think the chip in question, the ATtiny4313, has a hardware
>>> multiplier - so multiplication is also slow.  [snip other possible
>>> pitfalls]
>>
>> Thank you, this is quite helpful.  Probably the culprit here
>> is variable length shifts, which my code has a lot of.  But
>> I should be able to work around that.
>>
>> Do you by chance know what options to give gcc so that it targets
>> this architecture?  What I'm looking for in particular is having
>> gcc show generated assembly so I can look at that.
>>
>> Thank you again for the help!
>
> (I am not sure if you know all this and I've misunderstood your
> question slightly, or if it is new to you because you have little
> or no experience of cross-compilation.  So what I write here will
> either be helpful and interesting, or sound obvious and
> patronising.  Hopefully it will be the former!)

No worries - too much information is better than too little.

> Just to get you started with the AVR, beyond what I wrote earler:
>
> <https://en.wikipedia.org/wiki/Atmel_AVR>
>
> It's an 8-bit microcontroller architecture, made by Atmel.  The main
> product page is here:
>
> <http://www.atmel.com/products/microcontrollers/avr/default.aspx>
>
> (There is also an "AVR32" made by Atmel - it shares little with the AVR
> except the name.  Although the main compiler for the AVR32 is also gcc,
> it is outside the main gcc tree and maintained entirely by Atmel.
> Basically, the AVR32 is a dead-end architecture, since Atmel also make
> ARM microcontrollers - a shame really, since it was quite a nice cpu.
> So here we are only discussing the 8-bit AVR devices.)
>
> Pick a device if you want to see the datasheet and read about the cpu:
>
> <http://www.atmel.com/devices/ATMEGA3250.aspx?tab=documents>

Apparently pozz is targeting the tiny4314 rather than the mega3250.
But I can make those adjustments.

> Regarding the compiler, the gcc source supports the AVR (and a couple of
> dozen other architectures), but any given binary build is for a specific
> host-target combination.  So the gcc that you no doubt have installed on
> your system from before cannot target the AVR.  You can always download
> the gcc source and build it yourself, but probably you will do better to
> simply download the ready-build packages from Atmel:
>
> <http://www.atmel.com/tools/ATMELAVRTOOLCHAINFORLINUX.aspx>

I ended up using apt-get for gcc-avr (yes they switched the name),
which I think is enough for my original purposes.

> That gets you the compiler, binutils (assembler, linker, etc.), the
> library (avrlibc), device headers, etc.  The avrlibc project home page
> is another source of useful information:
>
> <http://www.nongnu.org/avr-libc/>

Is there by chance an emulator, hopefully one that can report
simulated timings?  I'm pretty much flying blind in terms of
performance results.

> Once you have the tools installed, a typical command line to
> compile a C file and look at the generated assembly would be:
>
> avr-gcc -mmcu=atmega3250 -c -Os -std=gnu11 -Wall -Wa,-adchls=test.lst test.c
>
> -mmcu=atmega3250 specifies the device (the format here may be
> different in newer avrgcc builds - it's a while since I used a new
> version, since I make a point of never changing toolchains in a
> project and I haven't had any recent AVR projects).  [snip]

The -mmcu=atmega3250 was the key piece of information I needed
(ie, beside knowing about avr-gcc as the compiler to use).  Like
I said I ended up using -mmcu=attiny4313, but same diff.  Also in
the compiler I got it was -S to generate assembly, but that was
no problem since I'm used to it with gcc generally.

Double thanks, this was great.

[toc] | [prev] | [next] | [standalone]

#76134

On 15/11/15 02:57, Tim Rentsch wrote:
> David Brown <david.brown@hesbynett.no> writes:
>

>> Just to get you started with the AVR, beyond what I wrote earler:
>>
>> <https://en.wikipedia.org/wiki/Atmel_AVR>
>>
>> It's an 8-bit microcontroller architecture, made by Atmel.  The main
>> product page is here:
>>
>> <http://www.atmel.com/products/microcontrollers/avr/default.aspx>
>>
>> (There is also an "AVR32" made by Atmel - it shares little with the AVR
>> except the name.  Although the main compiler for the AVR32 is also gcc,
>> it is outside the main gcc tree and maintained entirely by Atmel.
>> Basically, the AVR32 is a dead-end architecture, since Atmel also make
>> ARM microcontrollers - a shame really, since it was quite a nice cpu.
>> So here we are only discussing the 8-bit AVR devices.)
>>
>> Pick a device if you want to see the datasheet and read about the cpu:
>>
>> <http://www.atmel.com/devices/ATMEGA3250.aspx?tab=documents>
>
> Apparently pozz is targeting the tiny4314 rather than the mega3250.
> But I can make those adjustments.

Indeed.  I just used the Mega3250, as it's a chip I have used on a 
couple of projects.  (I once used a Tiny that has no ram at all - just 
the 32 8-bit registers.  Even then, I wrote the code in C using avr-gcc.)

>
>> Regarding the compiler, the gcc source supports the AVR (and a couple of
>> dozen other architectures), but any given binary build is for a specific
>> host-target combination.  So the gcc that you no doubt have installed on
>> your system from before cannot target the AVR.  You can always download
>> the gcc source and build it yourself, but probably you will do better to
>> simply download the ready-build packages from Atmel:
>>
>> <http://www.atmel.com/tools/ATMELAVRTOOLCHAINFORLINUX.aspx>
>
> I ended up using apt-get for gcc-avr (yes they switched the name),
> which I think is enough for my original purposes.

Yes, that will be good enough for what you want at the moment.

Like many embedded gcc targets, there are two ways to get the compiler - 
you can use the mainline gcc, or you can use the manufacturers fork. 
(In each case, you can get the source or use pre-built binaries, such as 
via apt-get or yum.)  The mainline version will give you the latest gcc 
features - the newest standards, the latest warnings, etc.  The forked 
version will give you the latest device support, the newest device 
headers, and workarounds for hardware bugs that might have been found. 
Changes done by the manufacturer in their fork will get passed back to 
mainline, but it can take some time before these are eventually in place 
in mainline releases.  And changes in mainline make it to the 
manufacturer's fork when they rebase.  (The same applies to the 
libraries involved.)

In general, for actual embedded development work, it is usually best to 
get the manufacturer's package of gcc, libraries, headers, and other 
utilities, examples, and documentation.  But in your case, it does not 
matter significantly - use whatever is most convenient.

>
>> That gets you the compiler, binutils (assembler, linker, etc.), the
>> library (avrlibc), device headers, etc.  The avrlibc project home page
>> is another source of useful information:
>>
>> <http://www.nongnu.org/avr-libc/>
>
> Is there by chance an emulator, hopefully one that can report
> simulated timings?  I'm pretty much flying blind in terms of
> performance results.

There is an open source AVR simulator, which is probably available in 
your apt-get repositories, and can work with the avr port of gdb.  I 
haven't used it myself.

There is also the full AVR Studio from Atmel with a simulator for the 
chips and many of their peripherals as well as the cpu.  It is a /big/ 
package - an MSVS IDE, pre-packaged gcc compiler, wizards, debugger, 
power estimator, everything you could wish for for AVR development, 
except support for anything other than Windows.  I haven't used it for a 
decade or so.

But performance calculations on the AVR are quite simple. 
Register-to-register instructions are all single cycle.  Accessing 
memory (read or write) takes another cycle.  Multi-byte instructions 
take an extra cycle per extra instruction word (the instruction memory 
is 16-bit wide, and on a separate bus from the data bus).  Branches take 
2 cycles when taken, 1 when not taken IIRC.

>
>> Once you have the tools installed, a typical command line to
>> compile a C file and look at the generated assembly would be:
>>
>> avr-gcc -mmcu=atmega3250 -c -Os -std=gnu11 -Wall -Wa,-adchls=test.lst test.c
>>
>> -mmcu=atmega3250 specifies the device (the format here may be
>> different in newer avrgcc builds - it's a while since I used a new
>> version, since I make a point of never changing toolchains in a
>> project and I haven't had any recent AVR projects).  [snip]
>
> The -mmcu=atmega3250 was the key piece of information I needed
> (ie, beside knowing about avr-gcc as the compiler to use).  Like
> I said I ended up using -mmcu=attiny4313, but same diff.  Also in
> the compiler I got it was -S to generate assembly, but that was
> no problem since I'm used to it with gcc generally.

"-S" asks gcc to generate an assembly file rather than to run the 
assembler directly, while "-Wa,-ahdl=test.lst" ask it to run the 
assembler but output an assembly listing file (with different options 
for things like macro expansion and other details).  Often the 
difference doesn't matter - but the "-Wa,-ahdl" method is neater when 
you want a listing file in addition to the normal object file.

You might like the -fverbose-asm flag too.


>
> Double thanks, this was great.
>

[toc] | [prev] | [next] | [standalone]

#76247

David Brown <david.brown@hesbynett.no> writes:

> On 15/11/15 02:57, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> [snipping a lot]
>
>> Is there by chance an emulator, hopefully one that can report
>> simulated timings?  I'm pretty much flying blind in terms of
>> performance results.
>
> There is an open source AVR simulator, which is probably available
> in your apt-get repositories, and can work with the avr port of
> gdb.  I haven't used it myself.

After I posted I got a reference to simulavr, which is indeed
available using apt-get.  However the apt-get version appears to
be an old one, so I loaded something directly from the simulavr
website. The earlier version didn't work with what I was trying
to do, but the later one did, and it reported a cycle count which
is all I needed.

>> The -mmcu=atmega3250 was the key piece of information I needed
>> (ie, beside knowing about avr-gcc as the compiler to use).  Like
>> I said I ended up using -mmcu=attiny4313, but same diff.  Also in
>> the compiler I got it was -S to generate assembly, but that was
>> no problem since I'm used to it with gcc generally.
>
> "-S" asks gcc to generate an assembly file rather than to run the
> assembler directly, while "-Wa,-ahdl=test.lst" ask it to run the
> assembler but output an assembly listing file (with different
> options for things like macro expansion and other details).  Often
> the difference doesn't matter - but the "-Wa,-ahdl" method is
> neater when you want a listing file in addition to the normal
> object file.

Oh, I tried the "-Wa,-ahdl=test.lst" method, but it didn't
produce anything.  Rather than try to figure out what was
going on I just used -S, which was sufficient for my
purposes.

Thank you again for the help.

[toc] | [prev] | [next] | [standalone]

#75951

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).

[toc] | [prev] | [next] | [standalone]

#76108

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.

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.

[toc] | [prev] | [next] | [standalone]

#76169

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.

[toc] | [prev] | [next] | [standalone]

#76273

pozz <pozzugno@gmail.com> writes:

> 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.

Here is a first step in the "hybrid strategy" direction.  I
made four changes:

   1. Used 'unsigned char' rather than 'unsigned' everywhere;
   2. Switched to the ending bit position of the first field
      rather than the starting bit position, which allows:
   3. A slightly simpler way of extracting the fields;  and
   4. A reworking of the subfunction that locates the end of
      the preamble to avoid variable length shifts.

Here is the code:

    unsigned char first_field_ending_point( unsigned char [8] );

    typedef unsigned char U8;

    unsigned char
    em4100_decode( unsigned char in[8], unsigned char out[5] ){
        U8 k = first_field_ending_point( in );
        U8 check, u, i;

        if(  k > 63  )  return  0;

        for(   i = 0,  check = 0,  u = 0;   i < 11;   i++,  k = k+5 & 63   ){
            U8 a     =  in[ k/8 +7 &7 ] << 1;
            U8 b     =  in[ k/8 ];
            U8 field =  (a << k%8  |  b >> 7-k%8)  &31;
            U8 data  =  field >> 1;

            if(  (field ^ 0x6996>>data) &1  &&  i < 10  )  return  0;

            check ^= data;
            u =  u << 4  |  data;
            if(  i % 2  )  out[ i/2 ] = u;
        }

        return  check == 0x0;
    }


    unsigned char
    first_field_ending_point( unsigned char in[8] ){
        U8  *d = in,  *dlast = d+7,  w = *d,  m = 128,  matched = 0,  j;

        if(  w & m  ){
            U8  v = *dlast;
            if(  v == 255  &&  dlast[-1] & 1  ){
                if(  w == 255  )  return  -1;
            } else {
                while(  v & 1  )  matched += 1,  v >>= 1;
            }
        }

        while(  matched = w & m ? matched+1 : 0,  matched != 9   ){
            if(       m != 1      )  m >>= 1;
            else if(  d == dlast  )  return  -1;
            else                     w = *++d,  m = 128;
        }

        j = 0;
        if(  m & 0x0F  )  j += 4;
        if(  m & 0x33  )  j += 2;
        if(  m & 0x55  )  j += 1;

        return  (d-in << 3) + j + 5  &63;
    }

Measurements with the simulavr simulator show this code to be
20 to 25 percent faster than the code you posted earlier.

I also have a completely rewritten version that has everything in
one function and does no variable length shifts, but I don't want to
post it because it still needs some readability cleanup.  The result
is a fair amount larger but also faster - measurements with simulavr
show the completely rewritten version to be more than twice as fast
as the improved code shown above.  But it takes up a lot more code
space so probably the code above is a better choice.

[toc] | [prev] | [next] | [standalone]

#76309

On 17/11/15 19:49, Tim Rentsch wrote:
<snip for brevity>
> Measurements with the simulavr simulator show this code to be
> 20 to 25 percent faster than the code you posted earlier.
>
> I also have a completely rewritten version that has everything in
> one function and does no variable length shifts, but I don't want to
> post it because it still needs some readability cleanup.  The result
> is a fair amount larger but also faster - measurements with simulavr
> show the completely rewritten version to be more than twice as fast
> as the improved code shown above.  But it takes up a lot more code
> space so probably the code above is a better choice.
>

It's fun trying to get optimal code on devices like this, isn't it?  It 
is very different from trying to get fast code on a desktop CPU, where 
you are concentrating on minimising cache misses and data dependencies. 
  On the AVR, everything is clear and regular, and every instruction 
counts.  The instruction set is simple enough that you can get the hang 
of all instructions and don't have to think about multiple ways to get 
the same calculation effect (but possibly different scheduling or 
pipeline units).

If you enjoy playing with the AVR, another architecture that might 
interest you is the msp430.  It is a 16-bit cpu with 16 registers and a 
very C-friendly ISA.

[toc] | [prev] | [next] | [standalone]

#76699

David Brown <david.brown@hesbynett.no> writes:

> On 17/11/15 19:49, Tim Rentsch wrote:
> <snip for brevity>
>> Measurements with the simulavr simulator show this code to be
>> 20 to 25 percent faster than the code you posted earlier.
>>
>> I also have a completely rewritten version that has everything in
>> one function and does no variable length shifts, but I don't want to
>> post it because it still needs some readability cleanup.  The result
>> is a fair amount larger but also faster - measurements with simulavr
>> show the completely rewritten version to be more than twice as fast
>> as the improved code shown above.  But it takes up a lot more code
>> space so probably the code above is a better choice.
>
> It's fun trying to get optimal code on devices like this, isn't
> it?  [...]

I think you should try your hand at coding this problem.  I would
greatly enjoy seeing what you come up with.

[toc] | [prev] | [next] | [standalone]

#74147

On Thursday, October 29, 2015 at 6:44:49 AM UTC, Tim Rentsch wrote:
>
>    D. Knowing the shift amount, don't bother to align the buffer,
>       but just extract the 10+1 fields directly out of shifted
>       data bytes.  It's a little bit tricky to figure out how to
>       do this but once you have the code to do it (ie, extract
>       one five bit field) is pretty short (the function I wrote
>       is kind of ugly, but just four lines).
> 

I can't quite rise to the heights of a four line function.
but here's my offering.

unsigned char readbits(unsigned char *buff, unsigned char index, unsigned char N)
{
  unsigned char first, second;
  unsigned char mask;
  signed char rshift;

  rshift = 8 - (index % 8) - N;
  first = buff[index/8];
  mask = ~(0xFF << N);
  if(rshift >= 0)
  {
     return (first >> rshift) & mask;
  }
  else
  {
     second = buff[index/8 + 1];
     return ((first << (-rshift)) | (second >> (8 + rshift))) & mask;
  }
}

[toc] | [prev] | [next] | [standalone]

#74323

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> On Thursday, October 29, 2015 at 6:44:49 AM UTC, Tim Rentsch wrote:
>
>>    D.  Knowing the shift amount, don't bother to align the buffer,
>>       but just extract the 10+1 fields directly out of shifted
>>       data bytes.  It's a little bit tricky to figure out how to
>>       do this but once you have the code to do it (ie, extract
>>       one five bit field) is pretty short (the function I wrote
>>       is kind of ugly, but just four lines).
>
> I can't quite rise to the heights of a four line function.
> but here's my offering.

The insight that helped me is to form a value
justified at the high end (eg, of an eight bit
temporary), and then shift right and mask.  You
might take another go and try using that idea.

[toc] | [prev] | [next] | [standalone]

#76171

For my beginner type of view 
Unprofessional etc
 I for first
would write a macro for find bit j
in a char
and a table
Something as
u8 Table[]={1,2,4,8,16,32,64,128};
so in the array of char I would know
if bit j of char in the array would be
#define bit(j,v) (table[j]&(v))
Without do division multiplication etc

But now I think that is possible to do
not only for char, but for u32 and u64
too
 is enough one "and" for to know
if bit j is 0 or 1

But first of this: Processor has one parity
instruction?

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web