// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License..

use std::alloc::Layout;
use std::ffi::c_void;
use std::fmt;
use std::mem;
use std::ptr;
use std::slice;

#[derive(Clone, Copy, Default)]
pub struct AlignReq {
    pub offset: usize,
    pub len: usize,
}

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct AlighAllocErr;

impl fmt::Display for AlighAllocErr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("memory allocation failed")
    }
}

#[derive(Clone, PartialEq, Eq, Debug)]
pub struct AlignLayoutErr;

impl fmt::Display for AlignLayoutErr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("invalid parameters to align Layout")
    }
}

pub fn pad_align_to(layout: Layout, align_req: &[AlignReq]) -> Result<Layout, AlignLayoutErr> {
    let pad = padding_needed_for(layout, align_req)?;
    let align = align_needed_for(layout, pad)?;
    Layout::from_size_align(pad + align + layout.size(), align).map_err(|_| AlignLayoutErr)
}

fn padding_needed_for(layout: Layout, align_req: &[AlignReq]) -> Result<usize, AlignLayoutErr> {
    if !check_layout(&layout) {
        return Err(AlignLayoutErr);
    }
    if !check_align_req(layout.size(), align_req) {
        return Err(AlignLayoutErr);
    }
    let bmp = make_bitmap(align_req);
    let offset = calc_lspc(layout.align(), bmp);
    if offset < 0 {
        Err(AlignLayoutErr)
    } else {
        Ok(offset as usize)
    }
}

fn align_needed_for(layout: Layout, offset: usize) -> Result<usize, AlignLayoutErr> {
    Ok(calc_algn(layout.align(), layout.size() + offset))
}

#[inline]
fn check_overflow(buf: usize, len: usize) -> bool {
    (buf + len < len) || (buf + len < buf)
}

fn check_layout(layout: &Layout) -> bool {
    if layout.size() == 0
        || !layout.align().is_power_of_two()
        || layout.size() > usize::MAX - (layout.align() - 1)
    {
        false
    } else {
        true
    }
}

fn check_align_req(size: usize, align_req: &[AlignReq]) -> bool {
    if align_req.len() == 0 {
        return false;
    }
    let len: usize = (size + 7) / 8;
    let bmp: &mut [u8] = unsafe {
        let ptr = libc::malloc(len) as *mut u8;
        if ptr.is_null() {
            return false;
        }
        ptr::write_bytes(ptr, 0, len);
        slice::from_raw_parts_mut(ptr, len)
    };

    for req in align_req {
        if check_overflow(req.offset, req.len) || (req.offset + req.len) > size {
            unsafe {
                libc::free(bmp.as_mut_ptr() as *mut c_void);
            }
            return false;
        } else {
            for i in 0..req.len {
                let offset = req.offset + i;
                if (bmp[offset / 8] & 1 << (offset % 8)) != 0 {
                    // overlap in req data
                    unsafe {
                        libc::free(bmp.as_mut_ptr() as *mut c_void);
                    }
                    return false;
                }
                let tmp: u8 = (1 << (offset % 8)) as u8;
                bmp[offset / 8] |= tmp;
            }
        }
    }
    true
}

fn gen_alignmask(al: usize, a: usize, m: u64) -> i64 {
    if a > al {
        gen_alignmask(al, (a >> 1) as usize, m | (m >> (a >> 1)))
    } else {
        m as i64
    }
}

#[inline]
fn __rol(v: u64, c: usize, m: usize) -> u64 {
    (v << (c & m)) | (v >> (((0 - c as isize) as usize) & m))
}

#[inline]
fn rol(v: i64, c: usize) -> i64 {
    __rol(v as u64, c, mem::size_of::<i64>() * 8 - 1) as i64
}

fn ror(v: i64, c: usize) -> i64 {
    rol(v, (0 - c as isize) as usize)
}

fn count_lzb(bmp: i64) -> i32 {
    if bmp == 0 {
        -1
    } else if bmp < 0 {
        0
    } else {
        count_lzb(bmp << 1) + 1
    }
}

fn calc_lspc(al: usize, bmp: i64) -> i32 {
    if !al.is_power_of_two() {
        -2
    } else {
        count_lzb(
            !(ror(bmp | ror(bmp, 1) | ror(bmp, 2) | ror(bmp, 3), 5) | ror(bmp, 1))
                & gen_alignmask(
                    al,
                    mem::size_of::<u64>() * 8,
                    1_u64 << (mem::size_of::<u64>() * 8 - 1),
                ),
        )
    }
}

fn __calc_algn(size: usize, a: usize) -> usize {
    if a > 8 && size <= a / 2 {
        __calc_algn(size, a / 2)
    } else {
        a
    }
}

fn calc_algn(al: usize, size: usize) -> usize {
    if al > 64 {
        al
    } else {
        __calc_algn(size, mem::size_of::<u64>() * 8)
    }
}

fn make_bitmap(align_req: &[AlignReq]) -> i64 {
    let mut bmp: i64 = 0;
    for req in align_req {
        if req.len > 63 {
            return -1;
        } else {
            bmp |= rol(((1 as i64) << req.len) - 1, req.offset);
        }
    }
    bmp
}

mod libc {
    use std::ffi::c_void;
    extern "C" {
        pub fn malloc(size: usize) -> *mut c_void;
        pub fn free(p: *mut c_void);
    }
}