function [y,idx] = bitrevorder(x)
%BITREVORDER Permute gpuArray input into bit-reversed order.
%   Y = BITREVORDER(X)
%   [Y,I] = BITREVORDER(X)
%
%   See also BITREVORDER, DIGITREVORDER, gpuArray.

% Copyright 2020-2023 The MathWorks, Inc.

% X must be a gpuArray which means it is definitely numeric or logical so
% no need to check. We do need to ensure it's 2D though.
if ~ismatrix(x)
    error(message('signal:digitrevorder:InvalidDimensions'));
end

if isvector(x)
    N = length(x);
else
    N = size(x,1);
end

% Check to make sure N is an integer power of radixbase:
nbits = log2(N);
if ((2^nbits) ~= N)
    error(message("signal:digitrevorder:MustBeInteger", "2"));
end

% Max index size for GPU is 2^32-1 so use uint32 for bit manipulation
idx = uint32(gpuArray.colon(1, N)');

idx = arrayfun(@iReverseIdxBits, idx, nbits);
if isvector(x)
    y = x(idx);
else
    y = x(idx,:);
end

% Make sure the index output is double if requested
if nargout>1
    idx = double(idx);
end

end

function y = iReverseIdxBits(idx, nbits)
y = zeros("like",idx);
newvalue = cast(2.^(nbits-1),"like",idx);
idx = idx - 1; % 1-based index to 0-based

% Note that every GPU thread does the same number of loop steps so this
% loop is actually pretty efficient.
for bit=1:nbits
    r = rem(idx,2);
    y = y + r*newvalue;
    idx = (idx-r)/2; % shift right
    newvalue = newvalue/2; % shift right
end
y = y + 1; % 0-based index to 1-based
end
