From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id A954746CE3 for ; Fri, 7 Jul 2023 17:22:37 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id BBFE068C755; Fri, 7 Jul 2023 20:22:34 +0300 (EEST) Received: from relay5-d.mail.gandi.net (relay5-d.mail.gandi.net [217.70.183.197]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id DC4C568C618 for ; Fri, 7 Jul 2023 20:22:27 +0300 (EEST) X-GND-Sasl: michael@niedermayer.cc Received: by mail.gandi.net (Postfix) with ESMTPSA id 4D1D31C0005 for ; Fri, 7 Jul 2023 17:22:27 +0000 (UTC) From: Michael Niedermayer To: FFmpeg development discussions and patches Date: Fri, 7 Jul 2023 19:22:16 +0200 Message-Id: <20230707172224.2368067-1-michael@niedermayer.cc> X-Mailer: git-send-email 2.31.1 MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH 1/9] avradio/sdr: use AVTree for candidate stations X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: This is needed so we can keep more information about stations without performance issues Signed-off-by: Michael Niedermayer --- libavradio/sdr.h | 4 +- libavradio/sdrdemux.c | 126 ++++++++++++++++++++++++++++++++++++------ 2 files changed, 110 insertions(+), 20 deletions(-) diff --git a/libavradio/sdr.h b/libavradio/sdr.h index 84abdbe1d9..4d6887a296 100644 --- a/libavradio/sdr.h +++ b/libavradio/sdr.h @@ -30,6 +30,7 @@ #include "libavutil/opt.h" #include "libavutil/time.h" #include "libavutil/thread.h" +#include "libavutil/tree.h" #include "libavutil/tx.h" #include "libavformat/avformat.h" @@ -131,8 +132,7 @@ typedef struct SDRContext { * Current list of detected stations, these can be overlapping and low quality detections. * Used for probing. Stations are not removed from this when added to station. */ - Station **candidate_station; - int nb_candidate_stations; + struct AVTreeNode *station_root; int width, height; int single_ch_audio_st_index; int waterfall_st_index; diff --git a/libavradio/sdrdemux.c b/libavradio/sdrdemux.c index d3f0368d7d..4ac360f71b 100644 --- a/libavradio/sdrdemux.c +++ b/libavradio/sdrdemux.c @@ -46,6 +46,7 @@ #include "libavutil/opt.h" #include "libavutil/time.h" #include "libavutil/thread.h" +#include "libavutil/tree.h" #include "libavutil/tx.h" #include "libavutil/xga_font_data.h" #include "libavcodec/kbdwin.h" @@ -118,6 +119,55 @@ static void free_station(Station *station) av_free(station); } +typedef struct FindStationContext { + double freq; + double range; + Station **station_list; + int station_list_size; + int nb_stations; +} FindStationContext; + +static int find_station_cmp(void *opaque, void *elem) +{ + FindStationContext *c = opaque; + Station *station = elem; + double distance = station->frequency - c->freq; + if (distance < -c->range) + return -1; + if (distance > c->range) + return 1; + return 0; +} + +static int find_station_enu(void *opaque, void *elem) +{ + FindStationContext *c = opaque; + if (c->nb_stations < c->station_list_size) { + c->station_list[c->nb_stations++] = elem; + } else + av_log(NULL, AV_LOG_WARNING, "find station reached list size of %d\n", c->station_list_size); + + return 0; +} + +/** + * Find stations within the given parameters. + * @param[out] station_list array to return stations in + * @param nb_stations size of station array + * @returns number of stations found + */ +static int find_stations(SDRContext *sdr, double freq, double range, Station **station_list, int station_list_size) +{ + FindStationContext find_station_context; + find_station_context.freq = freq; + find_station_context.range = range; + find_station_context.station_list = station_list; + find_station_context.station_list_size = station_list_size; + find_station_context.nb_stations = 0; + av_tree_enumerate(sdr->station_root, &find_station_context, find_station_cmp, find_station_enu); + return find_station_context.nb_stations; +} + static int create_station(SDRContext *sdr, Station *candidate_station) { enum Modulation modulation = candidate_station->modulation; double freq = candidate_station->frequency; @@ -165,14 +215,17 @@ static int create_station(SDRContext *sdr, Station *candidate_station) { best_station->timeout = 0; return best_station_index; } - for (i=0; inb_candidate_stations; i++) { + Station *station_list[1000]; + int nb_stations = find_stations(sdr, sdr->block_center_freq, sdr->sdr_sample_rate*0.5, station_list, FF_ARRAY_ELEMS(station_list)); + + for (i=0; icandidate_station[i]->frequency - freq); + double delta = fabs(station_list[i]->frequency - freq); // Station already added, or we have 2 rather close stations - if (modulation == sdr->candidate_station[i]->modulation && delta < freq_precission && sdr->candidate_station[i] != candidate_station) { + if (modulation == station_list[i]->modulation && delta < freq_precission && station_list[i] != candidate_station) { nb_candidate_match++; } - if (modulation != sdr->candidate_station[i]->modulation && delta < (bandwidth + sdr->candidate_station[i]->bandwidth)/2.1) + if (modulation != station_list[i]->modulation && delta < (bandwidth + station_list[i]->bandwidth)/2.1) nb_candidate_conflict++; } //if we have a recent conflict with an established station, skip this one @@ -225,18 +278,51 @@ static int create_station(SDRContext *sdr, Station *candidate_station) { static void create_stations(SDRContext *sdr) { - for(int i = 0; inb_candidate_stations; i++) { - Station *candidate_station = sdr->candidate_station[i]; - create_station(sdr, candidate_station); + Station *station_list[1000]; + + if (!sdr->block_center_freq) + return; + + int nb_stations = find_stations(sdr, sdr->block_center_freq, sdr->sdr_sample_rate*0.5, station_list, FF_ARRAY_ELEMS(station_list)); + + for(int i = 0; ifrequency > sb->frequency ) - (sa->frequency < sb-> frequency)) + +(sa->modulation > sb->modulation) - (sa->modulation < sb->modulation); +} + +static void *tree_insert(struct AVTreeNode **rootp, void *key, + int (*cmp)(const void *key, const void *b), + struct AVTreeNode **next) +{ + if (!*next) + *next = av_mallocz(av_tree_node_size); //FIXME check ENOMEM + return av_tree_insert(rootp, key, cmp, next); +} + +static void *tree_remove(struct AVTreeNode **rootp, void *key, + int (*cmp)(const void *key, const void *b), struct AVTreeNode **next) +{ + av_freep(next); + return av_tree_insert(rootp, key, cmp, next); +} + /** * remove stations which we no longer receive well * Especially with AM and weather conditions stations disapear, this keeps things a bit more tidy */ static void decay_stations(SDRContext *sdr) { + Station *station_list[1000]; + int nb_stations = find_stations(sdr, sdr->block_center_freq, sdr->bandwidth*0.5, station_list, FF_ARRAY_ELEMS(station_list)); + for (int i=0; inb_stations; i++) { Station *station = sdr->station[i]; @@ -252,12 +338,15 @@ static void decay_stations(SDRContext *sdr) } } - for (int i=0; inb_candidate_stations; i++) { - Station *station = sdr->candidate_station[i]; + for (int i=0; itimeout++ > CANDIDATE_STATION_TIMEOUT) { + struct AVTreeNode *next = NULL; + tree_remove(&sdr->station_root, station, station_cmp, &next); + av_freep(&next); + free_station(station); - sdr->candidate_station[i--] = sdr->candidate_station[--sdr->nb_candidate_stations]; } } } @@ -265,25 +354,26 @@ static void decay_stations(SDRContext *sdr) static int create_candidate_station(SDRContext *sdr, enum Modulation modulation, double freq, int64_t bandwidth, int64_t bandwidth_p2, float score) { Station *station; void *tmp; - - tmp = av_realloc_array(sdr->candidate_station, sdr->nb_candidate_stations+1, sizeof(*sdr->candidate_station)); - if (!tmp) - return AVERROR(ENOMEM); - sdr->candidate_station = tmp; + struct AVTreeNode *next = NULL; station = av_mallocz(sizeof(*station)); if (!station) return AVERROR(ENOMEM); - sdr->candidate_station[sdr->nb_candidate_stations++] = station; - station->modulation = modulation; station->frequency = freq; station->bandwidth = bandwidth; station->bandwidth_p2 = bandwidth_p2; station->score = score; - return sdr->nb_candidate_stations - 1; + tmp = tree_insert(&sdr->station_root, station, station_cmp, &next); + if (tmp && tmp != station) { + //unlikely + av_freep(&station); + } + av_freep(&next); + + return 1; } static void probe_common(SDRContext *sdr) -- 2.31.1 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe".