From patchwork Mon Jan 8 00:36:48 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: dmitry.gumenyuk@gmail.com X-Patchwork-Id: 7189 Delivered-To: ffmpegpatchwork@gmail.com Received: by 10.2.78.2 with SMTP id r2csp2049833jaa; Sun, 7 Jan 2018 16:37:40 -0800 (PST) X-Google-Smtp-Source: ACJfBovxNHQkUXpKDe8VEl6Wkxlfs/GmU2UFyS8u/+wWiD9bRGWYAgyP7/XYez3CPIO6mNhC+0bb X-Received: by 10.223.184.195 with SMTP id c3mr9559324wrg.9.1515371860219; Sun, 07 Jan 2018 16:37:40 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1515371860; cv=none; d=google.com; s=arc-20160816; b=qo6/Iswtxq8Zjo9ESp8O547JYozDQoErfDZkUF2s2Ld9ZlpOlX0gJb9NhZMaE7NhEf 3Xmx/REHPOIODkhLC9fUTRxyIFAIcwWHHbkSpzvYe8l78CuaeueP8+yRtVP3RdksS3sX VLCHMf/TsVbnFrsxN7xx4rdUwqnS/vA+7+IFBilMu2FoAocnglxxosB9ntquIOPMu+y+ Z9iOTnE+GU99N89UR9eP+RR6hrD4nSivOJewvdF2JuCGPMl3FlzInF3FUtj9MAHmNp2R whVF3uWhuEWwJ6itQMEAl9IudihfKPBJWiuBl+ruNDbu9qO+aJS6W8nf0JpgMXf4RNgo st5g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:content-transfer-encoding:cc:reply-to :list-subscribe:list-help:list-post:list-archive:list-unsubscribe :list-id:precedence:subject:mime-version:references:in-reply-to :message-id:date:to:from:dkim-signature:delivered-to :arc-authentication-results; bh=20qqJKWv5UFJDx4awn2iHyM1xfCqc3Vgykj07FHD8Dc=; b=Zh7GpPZPh6INUYz8keuic7eTZB7I5WdX/xXrO2nIBMJNNBeOI40Z8uZg+me+Uqov95 fYE+Mbw2TgvGeSA58kkhWB5mFWFxkvcA76hHbxXlMigyK8hO12y2p8KBJggmB6pWXuAY IUtOJoiKfYO/a3X/YCntjTG8+oQsVDkZsuh2sjIkLWclpKxZtjOZkx3ed8IedwWa2zKr EHpXnpNqHNpZKvkDEk9tpNgEtEXp1nRir3fFa95K1FYCY01b1n3OZHHUStC5eT5LqTJV 1xtbVZXOxjxEud8zKuuugeQ/8yaL+86EowVgyX6RKbBBG09K3DnbIYs4d9VFmuC7X6W5 fTgw== ARC-Authentication-Results: i=1; mx.google.com; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20161025 header.b=DeH7K2GN; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=gmail.com Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org. [79.124.17.100]) by mx.google.com with ESMTP id 36si6258609wrw.385.2018.01.07.16.37.39; Sun, 07 Jan 2018 16:37:40 -0800 (PST) Received-SPF: pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) client-ip=79.124.17.100; Authentication-Results: mx.google.com; dkim=neutral (body hash did not verify) header.i=@gmail.com header.s=20161025 header.b=DeH7K2GN; spf=pass (google.com: domain of ffmpeg-devel-bounces@ffmpeg.org designates 79.124.17.100 as permitted sender) smtp.mailfrom=ffmpeg-devel-bounces@ffmpeg.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=gmail.com Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id 74D77689F44; Mon, 8 Jan 2018 02:37:37 +0200 (EET) X-Original-To: ffmpeg-devel@ffmpeg.org Delivered-To: ffmpeg-devel@ffmpeg.org Received: from mail-lf0-f68.google.com (mail-lf0-f68.google.com [209.85.215.68]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id BCD4368049B for ; Mon, 8 Jan 2018 02:37:31 +0200 (EET) Received: by mail-lf0-f68.google.com with SMTP id h137so10417415lfe.8 for ; Sun, 07 Jan 2018 16:37:32 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=5bWHj33VjzkqYBtgKo5kX5FTqNYqTZW384jRTYGcQrc=; b=DeH7K2GNFi3FTqpFCuRAf2o3RA2rc/L/GHlvMIF6dJLJdXTjq0+cLOqWZFFcCabSLA /dDYv3vcZd8yrEZwYfjGs1oMfuhE1dtmtDpVB7g9VBsGxOQrpcEwBurYzYnK50UbMMqu Q1180t8NT71i417roHLX3+G4RG5Eq7IqToPHtmN8Aw3EOFUq4Uj+BCEFAVgLY6PdmZzJ 5U+YCNF5RuBdbyDmcwPrTvYnmP5ZxU8uqdhcDuNy1zlb9pCCtjJo1h8MWfTRjFJchw0C xE41ui7jzTVLhfOeBVBDjglJPtW9JmpK8DoFoVhHiE0vCyLa1CdASMvN9uF1DXaLUWZw GQvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=5bWHj33VjzkqYBtgKo5kX5FTqNYqTZW384jRTYGcQrc=; b=VONEQ3Elhrz8RcneEZwtercq03MwQidl4VFCbPcq1p60mO0X8ogjAJXnjsqilcZMdw svvEDkif0OFT44XP/t5GrO5yTrSH3lUKNLs2p/Dy/souZxJOE/b65xk05GUG7u7mWukD LRdx6P5HtZd6QPq1SkSmyVSwaS8j3dEU9nIntyrZKLdUFtyW9L5E9ARaHbgwsoie7QrV so/3pfLKlWZ5PNnvLHb2a647HuCTeY9KEASfJR4ZdW4vugBI6BPn+vXIGEGPT75KtLFc Kr5eQ38K9mx5VG3BAZDpyMaf/q5Ubza6fl6r0zArwd8HK6B7bY2yQt/8s1gDmk/RvMbB WnFA== X-Gm-Message-State: AKGB3mKLIlsl0auohEbVH6EMClUNpa+gFew/6n0oXdCHCC8TByGGS2CC CDG8GoobjUO2xu2ZIAQj5cfLFcE1 X-Received: by 10.46.124.13 with SMTP id x13mr5518253ljc.109.1515371851650; Sun, 07 Jan 2018 16:37:31 -0800 (PST) Received: from localhost.localdomain ([193.25.7.30]) by smtp.gmail.com with ESMTPSA id v63sm2126376lje.39.2018.01.07.16.37.30 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 07 Jan 2018 16:37:31 -0800 (PST) From: dmitry.gumenyuk@gmail.com To: ffmpeg-devel@ffmpeg.org Date: Mon, 8 Jan 2018 01:36:48 +0100 Message-Id: <20180108003648.99878-2-dmitry.gumenyuk@gmail.com> X-Mailer: git-send-email 2.14.3 (Apple Git-98) In-Reply-To: <20180108003648.99878-1-dmitry.gumenyuk@gmail.com> References: <20180108003648.99878-1-dmitry.gumenyuk@gmail.com> MIME-Version: 1.0 Subject: [FFmpeg-devel] [PATCH] avfilter: add dumpwave filter. 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 Cc: Dmytro Humeniuk Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" From: Dmytro Humeniuk Signed-off-by: Dmytro Humeniuk --- Changelog | 1 + libavfilter/Makefile | 1 + libavfilter/af_dumpwave.c | 273 +++++++++++++++++++++++++++++++++++++++++ libavfilter/allfilters.c | 1 + libavfilter/version.h | 4 +- tests/fate/filter-audio.mak | 5 + tests/ref/fate/filter-dumpwave | 1 + 7 files changed, 284 insertions(+), 2 deletions(-) create mode 100644 libavfilter/af_dumpwave.c create mode 100644 tests/ref/fate/filter-dumpwave diff --git a/Changelog b/Changelog index 61075b3392..40fd624449 100644 --- a/Changelog +++ b/Changelog @@ -38,6 +38,7 @@ version : - Removed the ffserver program - Removed the ffmenc and ffmdec muxer and demuxer - VideoToolbox HEVC encoder and hwaccel +- dumpwave audio filter version 3.4: diff --git a/libavfilter/Makefile b/libavfilter/Makefile index 256dfabd66..020d90ee01 100644 --- a/libavfilter/Makefile +++ b/libavfilter/Makefile @@ -122,6 +122,7 @@ OBJS-$(CONFIG_TREMOLO_FILTER) += af_tremolo.o OBJS-$(CONFIG_VIBRATO_FILTER) += af_vibrato.o generate_wave_table.o OBJS-$(CONFIG_VOLUME_FILTER) += af_volume.o OBJS-$(CONFIG_VOLUMEDETECT_FILTER) += af_volumedetect.o +OBJS-$(CONFIG_DUMPWAVE_FILTER) += af_dumpwave.o OBJS-$(CONFIG_AEVALSRC_FILTER) += aeval.o OBJS-$(CONFIG_ANOISESRC_FILTER) += asrc_anoisesrc.o diff --git a/libavfilter/af_dumpwave.c b/libavfilter/af_dumpwave.c new file mode 100644 index 0000000000..493b5b7ff2 --- /dev/null +++ b/libavfilter/af_dumpwave.c @@ -0,0 +1,273 @@ +/* + * Copyright (c) 2017 Dmytro Humeniuk + * + * 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 + * waveform audio filter – dumps RMS amplitude to JSON file like SoundCloud does + */ + +#include "libavutil/avassert.h" +#include "libavutil/avstring.h" +#include "libavutil/channel_layout.h" +#include "libavutil/opt.h" +#include "libavutil/parseutils.h" +#include "avfilter.h" +#include "formats.h" +#include "audio.h" +#include "internal.h" + +typedef struct DumpWaveContext { + const AVClass *class; + int w, h; + AVRational rate; + int col; + char *json; + char *str; + double *values; + int64_t c, n, max_samples; + double sum; /* sum of the squared samples per segment */ +} DumpWaveContext; + +#define OFFSET(x) offsetof(DumpWaveContext, x) +#define FLAGS AV_OPT_FLAG_AUDIO_PARAM|AV_OPT_FLAG_FILTERING_PARAM + +static const AVOption dumpwave_options[] = { + { "s", "set dump size", OFFSET(w), AV_OPT_TYPE_IMAGE_SIZE, {.str = "600x240"}, 0, 0, FLAGS }, + { "c", "set number of samples per item", OFFSET(c), AV_OPT_TYPE_INT64, {.i64 = 0}, 0, INT64_MAX, FLAGS }, + { "json", "set dump file", OFFSET(json), AV_OPT_TYPE_STRING, { .str = NULL }, 0, 0, FLAGS }, + { NULL } +}; + +AVFILTER_DEFINE_CLASS(dumpwave); + +static int config_output(AVFilterLink *outlink) +{ + DumpWaveContext *dumpwave = outlink->src->priv; + const int ch_width = dumpwave->w; + dumpwave->values = av_malloc(ch_width * sizeof(double)); + dumpwave->str = av_malloc(ch_width*sizeof(int)); + dumpwave->max_samples = dumpwave->c * outlink->channels; + + return 0; +} + +static av_cold void uninit(AVFilterContext *ctx) +{ + DumpWaveContext *dumpwave = ctx->priv; + const int ch_height = dumpwave->h; + const int ch_width = dumpwave->w; + char *result = dumpwave->str; + FILE *dump_fp = NULL; + + if (dumpwave->json && !(dump_fp = av_fopen_utf8(dumpwave->json, "w"))) + av_log(ctx, AV_LOG_WARNING, "dump failed.\n"); + + if (dump_fp) { + fprintf(dump_fp, "{\"width\":%d,\"height\":%d,\"samples\":[%s]}", ch_width, ch_height, result); + fclose(dump_fp); + } + av_freep(&dumpwave->str); + av_freep(&dumpwave->values); +} + +static int dumpwave_request_frame(AVFilterLink *outlink) +{ + AVFilterContext *ctx = outlink->src; + DumpWaveContext *dumpwave = ctx->priv; + const int ch_height = dumpwave->h; + const int ch_width = dumpwave->w; + const double *values = dumpwave->values; + char *result = dumpwave->str; + + AVFilterLink *inlink = ctx->inputs[0]; + int ret, val; + + ret = ff_request_frame(inlink); + if (ret == AVERROR_EOF) { + + char *pos = result; + + for(int i = 0; i < ch_width; i++) { + val = ch_height * values[i]; + if (val < 0 ) val = 0; + pos += sprintf(pos, "%d,", val); + } + pos[-1] = '\0'; //removing trailing comma + } + + return ret; +} + +static inline void calculate(DumpWaveContext *dumpwave, double smpl) +{ + double *sum = &dumpwave->sum; + double *values = dumpwave->values; + const int64_t max_samples = dumpwave->max_samples; + int *col = &dumpwave->col; + int64_t *n = &dumpwave->n; + + if (smpl != 0) + smpl = (20 * log10(fabs(smpl)) + 60) / 60; + + *sum += smpl*smpl; + + if ((*n)++ == max_samples) { + values[(*col)++] = sqrt(*sum / max_samples); + *sum = *n = 0; + } +} + +static int dumpwave_filter_frame(AVFilterLink *inlink, AVFrame *buf) +{ + AVFilterContext *ctx = inlink->dst; + DumpWaveContext *dumpwave = ctx->priv; + const int channels = inlink->channels; + + int i, c; + + switch (inlink->format) { + case AV_SAMPLE_FMT_DBLP: + for (c = 0; c < channels; c++) { + const double *src = (const double *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src); + } + break; + case AV_SAMPLE_FMT_DBL: { + const double *src = (const double *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src); + }} + break; + case AV_SAMPLE_FMT_FLTP: + for (c = 0; c < channels; c++) { + const float *src = (const float *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src); + } + break; + case AV_SAMPLE_FMT_FLT: { + const float *src = (const float *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src); + }} + break; + case AV_SAMPLE_FMT_S64P: + for (c = 0; c < channels; c++) { + const int64_t *src = (const int64_t *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src / (double)INT64_MAX); + } + break; + case AV_SAMPLE_FMT_S64: { + const int64_t *src = (const int64_t *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src / (double)INT64_MAX); + }} + break; + case AV_SAMPLE_FMT_S32P: + for (c = 0; c < channels; c++) { + const int32_t *src = (const int32_t *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src / (double)INT32_MAX); + } + break; + case AV_SAMPLE_FMT_S32: { + const int32_t *src = (const int32_t *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src / (double)INT32_MAX); + }} + break; + case AV_SAMPLE_FMT_S16P: + for (c = 0; c < channels; c++) { + const int16_t *src = (const int16_t *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src / (double)INT16_MAX); + } + break; + case AV_SAMPLE_FMT_S16: { + const int16_t *src = (const int16_t *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src / (double)INT16_MAX); + }} + break; + case AV_SAMPLE_FMT_U8P: + for (c = 0; c < channels; c++) { + const int8_t *src = (const int8_t *)buf->extended_data[c]; + + for (i = 0; i < buf->nb_samples; i++, src++) + calculate(dumpwave, *src / (double)INT8_MAX); + } + break; + case AV_SAMPLE_FMT_U8: { + const int8_t *src = (const int8_t *)buf->extended_data[0]; + + for (i = 0; i < buf->nb_samples; i++) { + for (c = 0; c < channels; c++, src++) + calculate(dumpwave, *src / (double)INT8_MAX); + }} + break; + } + return ff_filter_frame(ctx->outputs[0], buf); +} + +static const AVFilterPad dumpwave_inputs[] = { + { + .name = "default", + .type = AVMEDIA_TYPE_AUDIO, + .filter_frame = dumpwave_filter_frame, + }, + { NULL } +}; + +static const AVFilterPad dumpwave_outputs[] = { + { + .name = "default", + .type = AVMEDIA_TYPE_AUDIO, + .request_frame = dumpwave_request_frame, + .config_props = config_output + }, + { NULL } +}; + +AVFilter ff_af_dumpwave = { + .name = "dumpwave", + .description = NULL_IF_CONFIG_SMALL("Dumps RMS audio peaks to a json file"), + .uninit = uninit, + .priv_size = sizeof(DumpWaveContext), + .inputs = dumpwave_inputs, + .outputs = dumpwave_outputs, + .priv_class = &dumpwave_class, +}; diff --git a/libavfilter/allfilters.c b/libavfilter/allfilters.c index 753ae968aa..887c80c706 100644 --- a/libavfilter/allfilters.c +++ b/libavfilter/allfilters.c @@ -133,6 +133,7 @@ static void register_all(void) REGISTER_FILTER(VIBRATO, vibrato, af); REGISTER_FILTER(VOLUME, volume, af); REGISTER_FILTER(VOLUMEDETECT, volumedetect, af); + REGISTER_FILTER(DUMPWAVE, dumpwave, af); REGISTER_FILTER(AEVALSRC, aevalsrc, asrc); REGISTER_FILTER(ANOISESRC, anoisesrc, asrc); diff --git a/libavfilter/version.h b/libavfilter/version.h index 0f11721822..ca096962bb 100644 --- a/libavfilter/version.h +++ b/libavfilter/version.h @@ -30,8 +30,8 @@ #include "libavutil/version.h" #define LIBAVFILTER_VERSION_MAJOR 7 -#define LIBAVFILTER_VERSION_MINOR 11 -#define LIBAVFILTER_VERSION_MICRO 101 +#define LIBAVFILTER_VERSION_MINOR 12 +#define LIBAVFILTER_VERSION_MICRO 100 #define LIBAVFILTER_VERSION_INT AV_VERSION_INT(LIBAVFILTER_VERSION_MAJOR, \ LIBAVFILTER_VERSION_MINOR, \ diff --git a/tests/fate/filter-audio.mak b/tests/fate/filter-audio.mak index bd8b3d3c35..2da644a66f 100644 --- a/tests/fate/filter-audio.mak +++ b/tests/fate/filter-audio.mak @@ -347,3 +347,8 @@ fate-filter-formats: CMD = run libavfilter/tests/formats FATE_SAMPLES_AVCONV += $(FATE_AFILTER_SAMPLES-yes) FATE_FFMPEG += $(FATE_AFILTER-yes) fate-afilter: $(FATE_AFILTER-yes) $(FATE_AFILTER_SAMPLES-yes) + +FATE_AFILTER-$(call FILTERDEMDEC, DUMPWAVE, WAV, PCM_S16LE) += fate-filter-dumpwave +fate-filter-dumpwave: SRC = $(TARGET_PATH)/tests/data/asynth-44100-2.wav +fate-filter-dumpwave: CMD = ffmpeg -i $(SRC) -af dumpwave=s=1800x140:c=147:json=tests/data/fate/filter-dumpwave.out -f null - && cat tests/data/fate/filter-dumpwave.out + diff --git a/tests/ref/fate/filter-dumpwave b/tests/ref/fate/filter-dumpwave new file mode 100644 index 0000000000..bd07098ef8 --- /dev/null +++ b/tests/ref/fate/filter-dumpwave @@ -0,0 +1 @@ +{"width":1800,"height":140,"samples":[103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,102,104,103,102,104,104,102,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,102,104,103,102,104,104,102,103,104,102,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,102,104,104,102,103,104,102,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,102,103,104,102,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,102,104,103,103,103,104,103,103,104,103,103,104,103,103,104,103,103,103,104,103,103,104,103,103,104,103,102,104,103,102,104,103,102,103,104,102,103,104,103,101,104,105,104,103,102,104,104,102,102,103,104,104,103,103,104,104,102,103,103,103,104,103,103,103,104,102,104,103,103,104,103,103,103,103,103,103,103,103,103,104,103,103,103,104,103,103,103,103,104,103,103,103,103,103,103,103,104,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,104,104,103,103,103,103,103,103,103,103,103,103,103,102,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,104,103,103,105,103,103,103,103,103,103,104,103,103,103,104,103,103,103,104,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,106,106,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,100,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,96,98,100,97,99,98,97,97,97,96,98,97,98,97,99,98,97,95,98,97,98,101,96,95,96,94,97,99,99,95,98,96,98,98,98,98,98,98,99,98,96,97,99,97,98,99,99,99,96,98,97,98,98,99,99,97,100,95,98,97,99,94,98,96,99,98,97,99,98,97,96,98,95,96,97,100,99,96,99,97,97,97,99,98,97,96,97,97,99,99,100,95,99,98,95,96,99,97,99,99,95,98,96,97,96,99,96,97,98,96,97,95,97,99,99,96,99,96,98,98,96,96,97,96,99,98,97,98,100,98,100,96,98,98,99,97,99,99,99,97,99,97,99,99,98,96,100,97,95,112,119,121,121,118,122,122,120,121,123,121,120,118,121,120,121,123,124,122,120,124,121,122,121,120,121,122,122,120,119,118,122,121,122,121,120,123,120,121,122,121,121,119,120,119,120,121,121,120,122,120,122,123,122,124,122,120,122,121,121,119,122,123,123,122,120,121,119,123,121,125,119,121,119,120,121,121,121,123,122,120,122,123,120,120,123,121,119,122,120,122,123,121,123,121,121,123,120,120,121,123,123,120,122,122,119,120,122,122,120,122,122,120,123,120,121,120,121,121,123,120,121,119,122,117,124,122,122,119,120,122,121,121,123,121,120,121,122,120,121,123,121,119,123,120,123,125,121,120,121,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,104,103,104,103,103,104,103,104,103,104,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,104,103,104,102,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,104,103,103,103,104,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,104,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,103,104,103,103,103,103,103,103,103,102,81,75,74,74,75,76,78,78,79,81,81,82,84,84,84,86,86,86,87,88,88,88,90,88,89,90,89,89,90,89,89,89,89,88,88,89,87,87,87,85,85,85,83,83,82,81,80,79,78,76,75,75,73,75,80,76,79,75,74,74,76,77,77,79,81,80,82,84,83,84,86,86,86,88,87,87,89,89,88,89,90,89,89,90,89,89,90,89,88,89,88,87,87,87,86,85,86,84,83,83,81,80,80,78,77,76,75,73,74,76,81,81,76,73,74,75,76,76,79,79,80,82,83,83,84,85,85,86,87,87,87,89,88,88,90,89,89,89,90,89,89,90,89,89,89,88,87,88,87,86,86,86,84,84,84,82,81,81,78,77,77,75,74,74,74,79,76,79,74,74,75,75,76,78,78,80,81,82,82,84,84,85,86,87,86,87,89,88,88,90,89,89,90,89,89,90,89,89,89,89,88,88,89,87,86,87,85,84,85,83,82,82,81,79,79,78,75,75,75,73,75,81,80,76,74,74,75,76,77,78,79,81,81,82,84,84,84,86,86,86,88,88,87,88,89,88,89,90,89,89,90,89,89,90,89,88,89,88,87,87,87,85,85,85,83,83,83,81,80,80,78,76,75,75,73,74,78,76,79,75,74,74,75,77,77,79,80,80,82,84,83,84,86,85,86,88,87,87,89,89,88,89,90,89,89,90,89,89,90,89,88,89,88,87,88,87,86,86,85,84,83,83,81,80,80,78,77,76,75,74,74,75,81,80,77,73,74,75,75,76,79,79,80,82,82,83,84,85,85,86,87,87,87,89,88,88,90,89,89,90,90,89,89,90,89,89,89,88,88,88,87,86,86,85,84,84,83,82,81,81,79,78,78,75,74,75,74,77,76,80,75,74,74,75,76,78,78,80,81,81,82,84,84,85,86,87,86,87,88,88,88,90,89,89,90,89,89,90,89,89,89,89,88,88,89,87,87,87,85,84,85,83,82,82,81,79,79,78,76,75,75,73,75,80,81,76,75,74,75,76,77,78,79,81,81,82,84,84,84,86,86,86,88,88,87,89,89,88,89,90,89,89,90,89,89,90,89,88,89,88,87,87,87,85,85,86,83,83,83,81,80,80,78,77,76,75,73,74,77,78,79,76,74,74,75,76,77,79,80,80,82,83,83,84,86,85,86,88,87,87,89,88,88,90,89,89,90,90,89,89,90,89,88,89,88,87,88,87,86,86,85,84,84,83,81,81,80,78,77,77,75,74,74,75,80,81,78,74,74,75,75,76,79,79,80,82,82,82,85,85,85,86,87,86,87,89,88,88,90,89,89,90,89,89,90,90,89,89,89,88,88,88,87,86,87,85,84,0,0,0,0,0,0,0]}