Understanding Memory Stack Struct

Go To Last Post
23 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello AVR Freaks, I posted this but it seems to have dissipated so here goes second time lucky. 

 

So I am trying to completely understand a code that I have found online so that I can (hopefully) design it myself with understanding of what is happening. I am too stubborn to just use it! 

 

So below is part of the code for a ATTiny2313 that is used to build a MIDI to CV converter. I know that is using memory struct stacking?, but really don't understand what is happening. If anyone could be so kind and add any information or point me in the right direction I would greatly appreciate it. the design works with MIDI data coming in to the Ucontroller, which then goes to a DAC. If you are wondering what the mux is, the design has a PWM going to a multiplexer to create a portamento as well as some other PWM's creating other effects. Thank you in advance!!   Some of the comments are the creators, so dont be fooled in thinking I have an idea haha :)


void playnote(int note)
{
	PORTB = note;
	_delay_ms(100); // Call a 100ms delay
}

#define STACKSIZE 8

                                // A structure to represent a stack
struct Notestack {
	uint8_t data[STACKSIZE];	 // Maximum size of Stack
	uint8_t fill;				 // Create a byte called fill
	} notestack = {{},0};	     // clear notestack ??
int8_t match_pos = 0;			 // match position ???
uint8_t porta_mux= 0;			 // Port A Multiplexer ???

uint8_t to_stack(uint8_t input) {                // PUSH ?

	for(int8_t i=notestack.fill; i>=1; i--) {	//??
		notestack.data[i]=notestack.data[i-1];  // move each element in array to next place
	}
	notestack.data[0] = input;                  // insert new item at the top
	notestack.fill ++;                          // increment fill counter
	return notestack.fill;
}

uint8_t from_stack(uint8_t item_to_delete) {    // POP?

	for(int8_t i=notestack.fill-1; i>=0; i--) { 	// search backwards for item to remove (by value)
		if(notestack.data[i] == item_to_delete) {   // ??
			match_pos = i;
			break;
		}
	}

	for(int8_t i=match_pos; i<=notestack.fill-2; i++) {	// shift back by one pos everything after item_to_delete
		notestack.data[i] = notestack.data[i+1];
	}

	notestack.fill --;                                  //decrement fill counter
	return notestack.fill;
}

uint8_t last_active_key() {
	return notestack.data[0];                           // return new top element of key list
}

void make_gate() {
	if(notestack.fill >0) {
		PORTD |= (1<<6);                                // Turn on PD6 (Gate Output)
	}
	else {
		PORTD &= ~(1<<6);                                  // Turn off Gate Output
	}

}

/***************************************************************************************************************
DAC
***************************************************************************************************************/
// how is data being sent to the DAC?
void make_cv() {
	static uint8_t dac_value = 0;
	dac_value = (last_active_key()-36)<<1;
	PORTD &= ~(0b00111100);				// Put Port D bit 2,3,4,5 LOW
	PORTD |= (dac_value & 0x0F)<<2;
	PORTB &= ~(0b11100000);				//Put Port B bit 5,6,7 LOW
	PORTB |= (dac_value & 0xF0)<<1;
}

/***************************************************************************************************************
Portamento
***************************************************************************************************************/
// ??
void make_portamento(uint8_t setting) {
	if (setting <=2 ) {
		OCR1B = 1023;
		porta_mux=0;
	}
	else if(setting < 43+2) {
		porta_mux=1;
		OCR1B = 1024/(setting+1-2)-1;
	}
	else if(setting <= 43+2+43) {
		porta_mux=2;
		OCR1B = 1024/(setting+23+1-2-43)-1;
	}
	else {
		porta_mux=3;
		OCR1B = 1024/(setting+33+1-2-2*43)-1;
	}
}

 

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Not really sure what you are asking? Or what you don't understand?

 

All they are really doing here is connecting a counter of "how many used so far" to an array. It's a curious choice to call it "fill" but other than that it's not really any different to having separate:

	uint8_t data[STACKSIZE];	 // Maximum size of Stack
	uint8_t fill;				 // Create a byte called fill

but the struct{} just "ties them together" (which is bascially the purpose of structs). Now instead of just:

data[5] = 0xA5;
fill = 5;

you use:

notestack.data[5] = 0xA5;
notestack.fill = 5;

to denote the fact that both data items "belong" together in the group called "notestack".

 

If it helps to understand it just globally remove "notestack" and "notestack." and then the two items are unconnected. While you are at it rename "fill" to be "items_used_in_array" to make it even clearer. Something like:

void playnote(int note)
{
	PORTB = note;
	_delay_ms(100); // Call a 100ms delay
}

#define STACKSIZE 8

                                // A structure to represent a stack
uint8_t data[STACKSIZE];	 // Maximum size of Stack
uint8_t items_used;				 // Create a byte called items_used
int8_t match_pos = 0;			 // match position ???
uint8_t porta_mux= 0;			 // Port A Multiplexer ???

uint8_t to_stack(uint8_t input) {                // PUSH ?

	for(int8_t i=items_used; i>=1; i--) {	//??
		data[i]=data[i-1];  // move each element in array to next place
	}
	data[0] = input;                  // insert new item at the top
	items_used ++;                          // increment items_used counter
	return items_used;
}

uint8_t from_stack(uint8_t item_to_delete) {    // POP?

	for(int8_t i=items_used-1; i>=0; i--) { 	// search backwards for item to remove (by value)
		if(data[i] == item_to_delete) {   // ??
			match_pos = i;
			break;
		}
	}

	for(int8_t i=match_pos; i<=items_used-2; i++) {	// shift back by one pos everything after item_to_delete
		data[i] = data[i+1];
	}

	items_used --;                                  //decrement items_used counter
	return items_used;
}

uint8_t last_active_key() {
	return data[0];                           // return new top element of key list
}

As you can see they are treating the array as an 8 element "stack" and to_stack() and from_stack() are like PUSH and POP.

 

The fact that on "PUSH" they "shuffle" all the existing items in the stack to make room at [0] to add the new value is "costly"!

 

There are better ways to implement a "stack" in software!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you, you cleared up exactly where I was getting confused with. A few notes to add:

 

After that struct, the code states:  notestack = {{},0};

 

is that a equivalent of your alternative code having:

 

items_used = 0;

data = {};                     // which i'm guessing equals it to 0?

 

 

what betters ways are there to implement stack? if you think it is within my ability to translate this code to such methods ! 

 

thank you 

 

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JakkSynth wrote:
what betters ways are there to implement stack?

You start by walking in the footsteps of those that went before you.  I'd suggest a starting point of Donald Knuth's Art of Computer Programming Volume 1:  Fundamental Algorithms

 

Image result for donald knuth the art of computer programming volume 1

Chapter 2 – Information Structures

  • 2.1. Introduction
  • 2.2. Linear Lists
    • 2.2.1. Stacks, Queues, and Deques
    • 2.2.2. Sequential Allocation
    • 2.2.3. Linked Allocation
    • 2.2.4. Circular Lists
    • 2.2.5. Doubly Linked Lists
    • 2.2.6. Arrays and Orthogonal Lists
  • 2.3. Trees
    • 2.3.1. Traversing Binary Trees
    • 2.3.2. Binary Tree Representation of Trees
    • ...

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

is that a equivalent of your alternative code having:

That is what the author appears to have been trying to achieve but 2 things:

 

1) any global without an initial value given is guaranteed in the C standard to be initialised to 0 anyway (though I know one compiler that does not do this - well done TI!). So that initialisatoin stuff is not needed.

 

2) to be honest, even if .bss variables weren't guaranteed to be 0 then the only thing that MUST be set to 0 is "fill". Setting all of data[] to 0 is sup0erfluous in this case. (though I suppose it is "tidy").

JakkSynth wrote:
what betters ways are there to implement stack?
For that you want to read some of the classic texts from the gods of computing science:

 

https://en.wikipedia.org/wiki/Li...

 

People like  Edsger Dijkstra and Donald Knuth did the early research work in computer science and worked out "best ways" to do all the fundamental things like data structures, sorting, codecs, etc. Another notable you have probably heard of is  Alan Turing who famously created the concept of the Turing Machine which is actually a machine based solely around a stack (though he didn't concentrate on implementation). So all the research into "best ways to do XXXX" have already been explored (though modern day computer scientists continue to push the boundaries)

 

But in the short term Google is your friend. Just trying "best stack algorithm c" hits things like:

 

https://www.geeksforgeeks.org/st...

 

That is almost the same as the code you posted except that it does the far more obvious thing of adding new elements to the END of the array rather than "shuffling it" so that new stuff can be stored into "element 0".

 

But there are likely even better implementations such as linked lists which are not then limited to a fixed [8] size (or whatever) but grown and shrink dynamically as needed.

 

Another way is to use index registers in the CPU itself. They have pre-decrement and post-increment modes that are perfect for implementing something like a stack - the only issue you'd face is how such Asm might mix with the C (C compilers typically make use of index registers a lot themselves)

Last Edited: Thu. Mar 1, 2018 - 04:49 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

@JakkSynth wrote:

what betters ways are there to implement stack?

By implementing a queue instead.  I am not a musician, but I am fairly certain that notes are played in a particular order.  A stack is by definition a Last-In-First-Out (LIFO) memory structure.  A queue on the other hand, is a First-In-First-Out (FIFO) memory structure.

 

Beyond that, it is unclear to me why you would be taking elements out of the middle of either a stack or queue, and consequently rearranging the elements.  It defeats the purpose of using either in the first place.

Greg Muth

Portland, OR, US

Xplained/Pro/Mini Boards mostly

 

Make Xmega Great Again!

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Greg_Muth wrote:
By implementing a queue instead.
I wondered about that too! There is this:

uint8_t last_active_key() {
	return data[0];                           // return new top element of key list
}

but it does raise the question of why you'd want it. As you say you want to play in the order of "oldest first" not "newest first".

 

I did wonder about [8] too. If there's some reason you are "holding on to" notes rather than just playing the tone at the event then is a buffer that is only 8 deep going to be sufficient to cater for all that might occur?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Actually this is "odd" too:

void playnote(int note)
{
	PORTB = note;
	_delay_ms(100); // Call a 100ms delay
}

So it appears that all notes play for exactly the same length? Surely the whole point of MIDI is differing durations between note-on and note-off evens so a blanket _delay_ms(100) (which seems "arbitrary" and just plain slow!) looks wrong.

 

In fact the more you analyze all this the more it looks like an exercise in "how not to do stuff" !

 

PS I tried googling "notestack.data[i]=notestack.data[i-1];  // move each element in array to next place" to see if I could find somewhere on the internet this code came from (unique lines of C usually hit the source!) but find nada. So interested to hear where this code came from.

Last Edited: Thu. Mar 1, 2018 - 05:07 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

If I had a Stack, I'd name it Robert.

 

"Best"?  How can one answer that in a forum post?  What is the "best" route to take when driving from Boston to Los Angeles?  Surely that depends on many factors.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

Actually this is "odd" too:

void playnote(int note)
{
	PORTB = note;
	_delay_ms(100); // Call a 100ms delay
}

So it appears that all notes play for exactly the same length? Surely the whole point of MIDI is differing durations between note-on and note-off evens so a blanket _delay_ms(100) (which seems "arbitrary" and just plain slow!) looks wrong.

Seems to me that might've been a (terrible) way to achieve 75 BPM (beats per minute) with 8 eighth notes per beat. 10 per second x 60 seconds = 600. Divide that by 8 and you can achieve 75 BPM which can do 8 eighth notes per measure beat. A BPM of 75 is pretty standard for a slower track.

My digital portfolio: www.jamisonjerving.com

My game company: www.polygonbyte.com

Last Edited: Thu. Mar 1, 2018 - 06:08 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

So one thing that is confusing me (among the many), tell me where I am going wrong. 

 

The stack is an 8 element array. The variable "items_used" represents the amount of elements USED in the 8 element array. I assume that the initial value of items_used is 0. 

 

The for loop then states: if the no. of elements used is greater or equal to 1, Run the Loop and subtract 1 from the no. of elements used. 

 

However since the  items_used = 0, the loop will not run. 

 

It would make sense to me if items_used actually represented "amount of space available in stack". 

 

very confusing indeed haha 

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Original C code location: https://github.com/acidbourbon/m...

 

The Code working on the final Design: https://www.youtube.com/watch?v=...

 

If you are interested, my idea is to implement a similar idea, however to get the MIDI to CV to output exponential voltages (via the microcontroller somehow?) instead of relying on transistor matching and temperature compensation. A project I thought would be a great way to combine my love for music and desire to learn AVR. :) 

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JakkSynth wrote:
It would make sense to me if items_used actually represented "amount of space available in stack". 

Really?!

 

surprise

 

Surely, then name items_used is exactly the opposite of  "amount of space available in stack" ?

 

Space that has been used is no longer available - surely?

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I don't mean the name itself, I mean in the sense that the variable is used in the code. 

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You understand what a stack is? No doubt if you have had any computer science tuition someone has told you about the infamous spring loaded "stack of plates in a cafeteria" ?

 

With such a stack if the person operating the dish washer brings out 5 new plates and adds then one at a time to the stack then each one "pushes it down" by one plate at a time. So the "top plate" is always in the same place. That is pretty much what the author of this code has done in their to_stack() routine. There equivalent of that "spring loaded stack" that "moves down" each time a new plate is added on top is that "computationally expensive" thing that is happening in the for() loops. Sure. When the stack of plates is "empty" there is nothing to "move down" and that is represented by the for() loop ending immediately and not doing anything. But consider the case when there are now already three plates on the stack and you add a fourth. To keep the "top" plate in the same place (which in this case is data[0]) you need to move the 3 things already on the stack down by one. So plate 3 moves to plate 4, plate 2 moves to plate 3, plate 1 moves to plate 2 and the new plate goes on top.

 

In graphic form:

stack empty
| | | | | | |

to_stack(7)
|7| | | | | |

to stack(3)
|3|7| | | | |

to stack(8)
|8|3|7| | | |

to_stack(1)
7 is moved first
|8|3| |7| | |
3 is moved next
|8| |3|7| | |
8 moved next
| |8|3|7| | |
gap now opened so 1 can be inserted..
|1|8|3|7| | |

As you can see, as the stack grows more and more items have to be "moved down" by the for() loop. Now compare with the case where the stack grown the "other way":

stack empty
| | | | | | |

to_stack(7)
|7| | | | | |

to stack(3)
|7|3| | | | |

to stack(8)
|7|3|8| | | |

to_stack(1)
just plop the 1 on the end...
|7|3|8|1| | |

in this case there is no "shuffling" involved. Same goes for "pop" (or in this case from_stack()) if you call:

var = from_stack()
|7|3|8| | | |
now var = 1

again this does not involve shuffling data but in the implementation in the original code because it "put/take from front" then you have:

|1|8|3|7| | |
var = from_stack()
so var = 1 but now:
move 8 to front:
|8| |3|7| | |
move 3 to place where 8 was
|8|3| |7| | |
move 7 to place where 3 was
|8|3|7| | | |

Again all that "moving about" is being done using these expensive for loops. Of course when you get to:

|7| | | | | |
var = from_stack()
(so var = 7)
| | | | | | |

in this case there is no for() loop shuffling - in fact the amount of for() loop shuffling reduces each time something is removed from the stack.

 

I have no idea why the original code chose to implement a stack as it has.

 

But the other point in this thread is about what use this stack was. Suppose my numbers are keys on a musical keyboard. The user is tapping out a tune. So they tap notes 7 then 3 then 8 then 1. The stack now has 4 notes on it. But if you now "unstack" (that is "pop") the items from the stack you are going to play 1 then 8 then 3 then 7. That is the REVERSE ORDER to that in which the keys were hit in the first place. So a stack does not make any sense here. As Greg observed what you need is a FIFO (first in, first out). So he plays 7, 3, 8, 1 and then you recover and play these in the same 7, 3, 8, 1 order - surely that's what is needed here?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

PS forgot to mention "fill"/"item_used" or whatever you want to call it but:

stack empty fill = 0
| | | | | | |

to_stack(7) fill = 1
|7| | | | | |

to stack(3) fill = 2
|3|7| | | | |

to stack(8) fill = 3
|8|3|7| | | |

to_stack(1)
7 is moved first
|8|3| |7| | |
3 is moved next
|8| |3|7| | |
8 moved next
| |8|3|7| | |
gap now opened so 1 can be inserted.. fill = 4
|1|8|3|7| | |

The fill value can be used to determine how many "shuffles" the for() loop needs to do and where to start. Now fill = 4 at the end of this you know that if another item were to be added you need to move 4th to 5th, 3rd to 4th, 2nd to 3rd, 1st to 2nd and now you have a gap at the first position. That is done by:

	for(int8_t i=notestack.fill; i>=1; i--) {	//??
		notestack.data[i]=notestack.data[i-1];  // move each element in array to next place
	}

(remember that while I am a human (yeah it's true!) and tend to count things as 1st, 2nd, 3rd etc a computer (well C anyway) counts things from 0 so that's why it's using .fill an not .fill + 1 as a starting point).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
a stack does not make any sense here.

indeed.

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

JakkSynth wrote:
The for loop then states: if the no. of elements used is greater or equal to 1, Run the Loop and subtract 1 from the no. of elements used. However since the items_used = 0, the loop will not run.

No. Look at the counter of the loop, it is decrementing and the loop starts at items_used (the end of the stack) and goes towards 1. The loop stops at 1 because it moves index 1 to index 0. If it looped to 0, it would try to move index 0 to index -1 (since i is signed).

 

It is shifting each element of the array to the right. So the 0 index to is moved to 1, 1 is moved to 2, etc. This allows the new item to be put into index 0.

 

Think about the logic of the loop and write it down. It's very simple.

My digital portfolio: www.jamisonjerving.com

My game company: www.polygonbyte.com

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Also, just a note: This is an awful way to implement a stack. You shouldn't be moving all the numbers up and down, you should be keeping the index of the "top" member, and moving the index.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Im a going to implement the suggested way of writing the Stack. Thank you everyone for your kind advice. Before doing so I will completely understand what this is doing. I guess the only purpose for the designer to do it this way was so the Top position (Index 0) does not change, which in turn will be the note that is always played.   

 

It makes sense to me when the items are moved to the right. But correct me if I am wrong:

 

notestack.data[i]=notestack.data[i-1];	

would this action not move each item to the left?

JT

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

would this action not move each item to the left?

If you're standing on your head, yes.   Replacing i and i-1 with actual values:

notestack.data[3]=notestack.data[2];
notestack.data[2]=notestack.data[1];	
notestack.data[1]=notestack.data[0];	

Looks like the values are moving to the right to me. 

Greg Muth

Portland, OR, US

Xplained/Pro/Mini Boards mostly

 

Make Xmega Great Again!

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Step back and ask "is it a stack (LIFO) that is needed here anyway?". The answer is almost certainly "no".

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I am re-writing the stack section of the code in FIFO as advised so i'll show you my best attempt when I feel i have given it my all. Does anyone have an idea why the last_active_key is subtracted by 32 and shifted then shifted to the left? As well as the other line of code with the question marks! 

 

void make_cv() {
	static uint8_t dac_value = 0;     
           
	dac_value = (last_active_key()-36)<<1;        //   ?? 
	PORTD &= ~(0b00111100);				          
	PORTD |= (dac_value & 0x0F)<<2;               //   ??
	PORTB &= ~(0b11100000);				         
	PORTB |= (dac_value & 0xF0)<<1;
}

For the first line of code. I'm thinking it has something to do with NOTE_ON, as NOTE_ON in MIDI is equal to 0b10010000. And 36 in binary is 0b100100. 

 

I understand that PORTD and PORTB are changing the HIGH and LOW of the outputs

 

JT