From patchwork Thu Aug 8 08:36:45 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Michael Niedermayer X-Patchwork-Id: 14311 Return-Path: X-Original-To: patchwork@ffaux-bg.ffmpeg.org Delivered-To: patchwork@ffaux-bg.ffmpeg.org Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by ffaux.localdomain (Postfix) with ESMTP id A7CC9449C5F for ; Thu, 8 Aug 2019 11:39:52 +0300 (EEST) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 6961F68AB43; Thu, 8 Aug 2019 11:39:52 +0300 (EEST) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from vie01a-dmta-pe05-1.mx.upcmail.net (vie01a-dmta-pe05-1.mx.upcmail.net [84.116.36.11]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id C070068A9D8 for ; Thu, 8 Aug 2019 11:39:45 +0300 (EEST) Received: from [172.31.216.235] (helo=vie01a-pemc-psmtp-pe12.mail.upcmail.net) by vie01a-dmta-pe05.mx.upcmail.net with esmtp (Exim 4.92) (envelope-from ) id 1hvdxZ-000A0A-3Q for ffmpeg-devel@ffmpeg.org; Thu, 08 Aug 2019 10:39:45 +0200 Received: from localhost ([213.47.41.20]) by vie01a-pemc-psmtp-pe12.mail.upcmail.net with ESMTP id vdvJhe9ACwlysvdvJhNv3c; Thu, 08 Aug 2019 10:37:26 +0200 X-Env-Mailfrom: michael@niedermayer.cc X-Env-Rcptto: ffmpeg-devel@ffmpeg.org X-SourceIP: 213.47.41.20 X-CNFS-Analysis: v=2.3 cv=E5OzWpVl c=1 sm=1 tr=0 a=I1eytVlZLDX1BM2VTtTtSw==:117 a=I1eytVlZLDX1BM2VTtTtSw==:17 a=MKtGQD3n3ToA:10 a=1oJP67jkp3AA:10 a=GEAsPZ9sns4A:10 a=ZZnuYtJkoWoA:10 a=PUnBfP-k-14yJyfSdikA:9 From: Michael Niedermayer To: FFmpeg development discussions and patches Date: Thu, 8 Aug 2019 10:36:45 +0200 Message-Id: <20190808083646.18391-1-michael@niedermayer.cc> X-Mailer: git-send-email 2.22.0 MIME-Version: 1.0 X-CMAE-Envelope: MS4wfOb3jBoSDmHBhbjadlT9UYx/7cTwShiiRb/wDnydykyrbpBFbIEuFmmX0Ts1sNOTxbiTxTSyOrJ284JIWW7/oAkfq/qmbHL/ZGaXCgi69KLLhzAg2WTG 9jpHQlWNtdaQQKWVXCmQjVKRjlfeMnT+hnVDyFbPjh9oPcVMhoHYgcip Subject: [FFmpeg-devel] [PATCH 1/2] avutil: Add Simple loop detector X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.20 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 Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" This provides an alternative to retry counters. Useful if there is no reasonable maximum number of iterations and no ordering that naturally avoids loops. Signed-off-by: Michael Niedermayer --- doc/APIchanges | 3 ++ libavutil/Makefile | 1 + libavutil/loop_detector.h | 71 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 75 insertions(+) create mode 100644 libavutil/loop_detector.h diff --git a/doc/APIchanges b/doc/APIchanges index 6603a8229e..eee4c30ec5 100644 --- a/doc/APIchanges +++ b/doc/APIchanges @@ -15,6 +15,9 @@ libavutil: 2017-10-21 API changes, most recent first: +2019-XX-XX - XXXXXXXXXX - lavu 56.XX.XXX - loop_detector.h + Add loop_detector.h, av_is_loop(), AVSimpleLoopDetector + 2019-07-27 - xxxxxxxxxx - lavu 56.33.100 - tx.h Add AV_TX_DOUBLE_FFT and AV_TX_DOUBLE_MDCT diff --git a/libavutil/Makefile b/libavutil/Makefile index 57e6e3d7e8..0b77fa6347 100644 --- a/libavutil/Makefile +++ b/libavutil/Makefile @@ -48,6 +48,7 @@ HEADERS = adler32.h \ intreadwrite.h \ lfg.h \ log.h \ + loop_detector.h \ macros.h \ mathematics.h \ mastering_display_metadata.h \ diff --git a/libavutil/loop_detector.h b/libavutil/loop_detector.h new file mode 100644 index 0000000000..6f8643495a --- /dev/null +++ b/libavutil/loop_detector.h @@ -0,0 +1,71 @@ +/* + * Copyright (C) 2019 Michael Niedermayer (michael@niedermayer.cc) + * + * This file is part of FFmpeg + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + + +/** + * @file + * Utilties for detecting infinite loops + * @author Michael Niedermayer + */ + +#ifndef AVUTIL_LOOP_DETECTOR_H +#define AVUTIL_LOOP_DETECTOR_H + +typedef struct AVSimpleLoopDetector { + uint64_t count; + uint64_t state; +} AVSimpleLoopDetector; + +/** + * Checks if the list of states provided by the user fell into a cycle. + * + * To initialize or reset the detector, the context is simply memset to 0. + * This detector requires only 16bytes of context and minimal computations + * per iteration. In exchange for this simplicity it takes a few iterations + * into a loop before it is detected. + * No deallocation or memory allocation is needed. + * + * @param c The context, initialy and to reset, it is simply memset to 0. + * It is only 16bytes so as to be lightweight and not poison any + * data cache. + * + * @param state The loop state, when this falls into a cycle the detector + * will after a few iterations return 1. + * + * @param max_iterations + * after this many iterations the detector will return 1 regardless + * of it falling into a cycle. + * + * @return 1 if a loop is detected, 0 otherwise, no errors are possible. + * The code will always return 1 once it returned 1 until its reset. + */ +static inline int av_is_loop(AVSimpleLoopDetector *c, uint64_t state, uint64_t max_iterations) +{ + if (c->count && c->state == state) + c->count = max_iterations; + if (c->count >= max_iterations) + return 1; + c->count ++; + if (!(c->count & (c->count - 1))) + c->state = state; + return 0; +} + +#endif /* AVUTIL_LOOP_DETECTOR_H */