{"action":"created","issue":{"url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112","repository_url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh","labels_url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112/labels{/name}","comments_url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112/comments","events_url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112/events","html_url":"https://github.com/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112","id":156771527,"number":112,"title":"fifo with size!=2^n","user":{"login":"victorpasse","id":7287350,"avatar_url":"https://avatars.githubusercontent.com/u/7287350?v=3","gravatar_id":"","url":"https://api.github.com/users/victorpasse","html_url":"https://github.com/victorpasse","followers_url":"https://api.github.com/users/victorpasse/followers","following_url":"https://api.github.com/users/victorpasse/following{/other_user}","gists_url":"https://api.github.com/users/victorpasse/gists{/gist_id}","starred_url":"https://api.github.com/users/victorpasse/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/victorpasse/subscriptions","organizations_url":"https://api.github.com/users/victorpasse/orgs","repos_url":"https://api.github.com/users/victorpasse/repos","events_url":"https://api.github.com/users/victorpasse/events{/privacy}","received_events_url":"https://api.github.com/users/victorpasse/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-05-25T14:53:40Z","updated_at":"2016-05-25T15:47:14Z","closed_at":null,"body":"Hi, I want a fifo size of 40 for several of the fifos but do not want to waste ram to have 64.\r\nWhat do i need to change for this to work?\r\nIs it only where you do operations like this:\r\n& (p_fifo->array_len - 1)\r\nor are other parts of the code dependent of size=2^n?"},"comment":{"url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/comments/221618564","html_url":"https://github.com/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112#issuecomment-221618564","issue_url":"https://api.github.com/repos/NordicSemiconductor/nRF51-ble-bcast-mesh/issues/112","id":221618564,"user":{"login":"trond-snekvik","id":7857838,"avatar_url":"https://avatars.githubusercontent.com/u/7857838?v=3","gravatar_id":"","url":"https://api.github.com/users/trond-snekvik","html_url":"https://github.com/trond-snekvik","followers_url":"https://api.github.com/users/trond-snekvik/followers","following_url":"https://api.github.com/users/trond-snekvik/following{/other_user}","gists_url":"https://api.github.com/users/trond-snekvik/gists{/gist_id}","starred_url":"https://api.github.com/users/trond-snekvik/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/trond-snekvik/subscriptions","organizations_url":"https://api.github.com/users/trond-snekvik/orgs","repos_url":"https://api.github.com/users/trond-snekvik/repos","events_url":"https://api.github.com/users/trond-snekvik/events{/privacy}","received_events_url":"https://api.github.com/users/trond-snekvik/received_events","type":"User","site_admin":false},"created_at":"2016-05-25T15:47:14Z","updated_at":"2016-05-25T15:47:14Z","body":"Hi,\r\nThis is possible, but requires some changes to the fifo implementation. To understand why, we have to understand how index overflow works in the fifo:\r\n\r\nInstead of rolling over the head and tail indexes when they hit fifo length, the fifo implementation assumes that indexes will naturally overflow on a multiple of the fifo size. \"Dumb\" fifo implementations keeps the indexes inside the fifo size. This forces us to waste a slot in the fifo, as the case where `head == tail` will be ambiguous (is the queue empty or full?), and we have to say that the fifo is full when `tail == head - 1`. If we let the indexes wrap at `fifo_size * N` (for `N>1`), and modulo the \"raw\" index on the fifo size on lookup, we can get rid of the ambiguity, as the fifo is guaranteed to be empty when `head == tail`, and full when `head == tail + fifo_size` (see the defines at L39 and L40 in [fifo.c](https://github.com/NordicSemiconductor/nRF51-ble-bcast-mesh/blob/master/nRF51/rbc_mesh/src/fifo.c#L39)).\r\n\r\nThere are two problems with doing non-power of two:\r\n\r\n1. You have to do modulo instead of bitwise and to get the buffer index, which will be significantly slower. \r\n\r\n2. You have to solve index rollover, as it will no longer be aligned with the natural rollover of the data type.\r\n\r\nAn alternative solution would be to bite the bullet, and keep the indexes inside the fifo size, then do `if (index > size) index -= size;` on each iteration. This costs you a slot in the fifo, but if you're hitting 40+ slots, it doesn't really matter that much."}}
{"actor":{"display_login":"trond-snekvik"}}